12865: 평범한 배낭
문제 설명
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
문제 풀이
탐욕법인 줄 알았는데 동적계획법이었다.
n, k = map(int, input().split())
thing = [[0,0]]
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(n):
thing.append(list(map(int, input().split())))
for i in range(1, n+1):
for j in range(1, k+1):
w = thing[i][0]
v = thing[i][1]
if j < w:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
print(dp[n][k])
13549: 숨바꼭질3
문제 설명
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
from collections import deque
n, k = map(int, input().split())
q = deque()
q.append(n)
visited = [-1 for _ in range(100001)]
visited[n] = 0
while q:
s = q.popleft()
if s == k:
print(visited[s])
break
if 0 <= s-1 < 100001 and visited[s-1] == -1:
visited[s-1] = visited[s] + 1
q.append(s-1)
if 0 < s*2 < 100001 and visited[s*2] == -1:
visited[s*2] = visited[s]
q.appendleft(s*2)
if 0 <= s+1 < 100001 and visited[s+1] == -1:
visited[s+1] = visited[s] + 1
q.append(s+1)
1504: 특정한 최단 경로
문제 설명
https://www.acmicpc.net/problem/1504
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
14891: 톱니바퀴
문제 설명
https://www.acmicpc.net/problem/14891
14891번: 톱니바퀴
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴
www.acmicpc.net
1918: 후위 표기식
문제 설명
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식
www.acmicpc.net
a = input()
stack = []
answer = ''
for x in a:
if x.isalpha():
answer += x
else:
if x == '(':
stack.append(x)
elif x == '*' or x =='/':
while stack and (stack[-1]=='*' or stack[-1]=='/'):
answer += stack.pop()
stack.append(x)
elif x == '+' or x == '-':
while stack and stack[-1] != '(':
answer += stack.pop()
stack.append(x)
elif x == ')':
while stack and stack[-1] != '(':
answer += stack.pop()
stack.pop()
while stack:
answer += stack.pop()
print(answer)'알고리즘 문제 > 백준' 카테고리의 다른 글
| 백준 14719번: 빗물 python 풀이 및 정답 코드 (0) | 2021.10.30 |
|---|---|
| 백준 2504번: 괄호의 값 python 풀이 및 정답 코드 (0) | 2021.10.30 |
| 백준 14888번: 연산자 끼워넣기 python 풀이 및 정답 코드 (0) | 2021.10.30 |
| [백준] 2609, 2693, 1978, 1292, 2581번 파이썬 풀이 (1) | 2021.09.25 |
| [백준] 2406, 2501, 3460, 10818, 10870 파이썬 풀이 (0) | 2021.09.12 |