음식물 피하기 (실버 1)
그래프의 요소는 음식물 or 빈공간 즉 0 아니면 1이다. 1인 경우 모든 연결된 1을 방문해야 한다. 그러므로 DFS, BFS 어느 것을 써도 상관 없다. 한번의 검색시 모든 인접 유효 요소를 방문하고 방문플랜에 들어갈 때 마다, 방문한 정보를 저장하고, 카운트를 올린다. 이것을 함수화 하여 카운트를 리턴한다. 기존의 카운트와 max()로 비교하여 갱신한다. 모든 과정이 끝나면 해당 count가 가장 큰 음식물의 부피(음식물 연결이 가장 많은 것)일 것이다.
from queue import Queue
from sys import stdin
row, col, n = map(int, stdin.readline().split())
map_lst = [[0] * (col) for _ in range(row)]
visited = [[0] * (col) for _ in range(row)]
for i in range(n):
x, y = map(int, stdin.readline().split())
x = x - 1
y = y - 1
map_lst[x][y] = 1
def search_tool(start_row, start_col, map_lst, visited):
q = Queue()
q.put((start_row, start_col))
visited[start_row][start_col] = 1
power = 1
can_go = [(-1,0),(1,0),(0,-1),(0,1)]
while not q.qsize() == 0:
row, col = q.get()
for i in can_go:
if 0 <= row + i[0] < len(map_lst) and 0 <= col + i[1] < len(map_lst[0]):
if visited[row + i[0]][col + i[1]] == 0 and map_lst[row + i[0]][col + i[1]]:
q.put((row + i[0], col + i[1]))
visited[row + i[0]][col + i[1]] = 1
power += 1
return visited, power
power = 0
for i in range(row):
for j in range(col):
if map_lst[i][j] == 1 and visited[i][j] == 0:
visited, power_new = search_tool(i, j, map_lst, visited)
power = max(power, power_new)
print(power)동전 1 (골드 5)
감이 안올 수 있다. 경우의 수를 . 다 직접계산으로 구하자기에는 입력 조건을 보면 시간초과나 메모리가 부담스럽다. 아마 중복된 계산을 줄여서 접근하는 다이나믹 프로그래밍 방법일 것이다.
문제에서 구하는 것은 가치의 합이 k원이 되도록 하는 경우의 수다. k를 dp의 인덱스로 하여 0부터 직접 써보기로 한다.
동전의 종류가 1, 2, 5일 때
dp[0] = 1 (숫자조합 없음, 한가지 경우의 수)
dp[1] = 1 (0+1)
dp[2] = 2 (0+1+1, 0+2)
dp[3] = 2 (0+1+1+1, 0+2+1)
dp[4] = 3 (0+1+1+1+1, 0+2+1+1, 0+2+2)
쓰다보니 중복을 피할 단서를 발견한다. 예로, dp[4]의 경우 dp[3]의 모든 요소에 1씩 더해서 그대로 반영중이다. 동전에 1이 존재해서 그럴 수 있다. 그렇게 생각해보니, 만약 가치의 합이 k원이니, dp[k]는 dp[k-2]와 비슷하다는 느낌과 또한 dp[k]는 dp[k-5]와 비슷할 수 있다는 것 왜냐면 dp[k-2]인 모든 요소에 2씩 더해주면 된다. dp[k-5]에도 동일하다.
dp는 인덱스가0인 것 빼고는 처음에 모두 0으로 초기화 되어있다. 그러므로 일단은 채워야 한다. dp[k-2], dp[k-5], dp[k-1]을 한번에 작동시키면 0만 참고하니 실패다.
하나의 동전에 대해 한 싸이클씩 동전의 수만큼 for문 사이클을 돌리면 성공할 듯 하다.
from sys import stdin
n, k = map(int, stdin.readline().split())
coins = []
dp = [0]*(k+1)
dp[0] = 1
for i in range(n):
coins.append(int(stdin.readline()))
for coin in coins:
for i in range(coin, k+1):
dp[i] = dp[i] + dp[i-coin]
print(dp[k])동전 2 (골드 5)
동전 1과 같은 입력을 준다. 단지 구하는 것이 경우의 수가 아닌 연산 횟수의 최솟값이다. dp문제임은 바로 직감이 되었으니 점화식을 세워보자.
위에서 가진 감각을 살리면 바로 점화식이 나온다. dp[k]를 판단하기 위해 dp[k-5원]을 생각하면 된다. 만약 내가 타겟하고 있는 것이 5원일 때 라면, dp[k-5]에 K = k-5일때의 연산횟수의 최솟값이 저장되어있다고 한다면, 거기에 + 1 한 값을 활용하면 된다. 이 값을 기존값과 min()연산 해주면 된다.
그러므로 점화식은 다음과 같다.
- d[i] = min(d[i], d[i-coin] + 1)
from sys import stdin
n, k = map(int, stdin.readline().split())
coins = []
dp = [(k+10)]*(k+1)
dp[0] = 1
for i in range(n):
coins.append(int(stdin.readline()))
coins = list(set(coins))
for coin in coins:
for i in range(coin, k+1):
dp[i] = min(dp[i], dp[i-coin] + 1)
if dp[k] == k + 10:
print(-1)
else:
print(dp[k] - 1)/// 드디어 골드 문제들 입성, 크게 어렵지는 않지만 실버 상위 티어보다 조금 이해를 어렵게 하기위해 꼬은 느낌이다.
