문제 바로가기
문제:
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다. 자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.
입력:
첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.
출력:
첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.
근래 풀었던 문제중에 제일 어려웠던거 같다. 바로dp
요즘 다른 친구들 기업들 코테를 푸는거 보면 Dp가 거의 필수다.
이 문제를 처음 접했을때 당연히 3차원 Dp라고 생각했다.
dp = [자두나무위치][떨어지는시간][움직인횟수]
그리고 단순하게 자두나무가 1번나무에 떨어질 경우와, 2번나무에 떨어지는 경우를 나눠서 최댓값을 구하면 된다
나는 2차원 dp를 사용했다
Dp = [떨어지는시간][사용횟수]
각 떨어지는 시간 마다 사용횟수갯수만큼 둔다.
예를들어 7, 2이면
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
이렇게 나오는데 각 나무의 몇번 이동횟수 마다 모든 갯수를 최신화 한다.
시작위치는 1번의 위치이다.
0번 이동했으면 1번나무 아래, 1번 이동했으면 2번 나무아래가 된다.
짝수번 움직였으면 무조건 1번나무아래, 홀수번이면 무조건 2번 나무 아래가 된다.
그러면 dp의 점화식은
i-1 번째 나무까지 j번 이하 움직임으로 얻은 자두 갯수 + 지금자리에서 얻은 자두 개수를 더하면 된다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
t, w = map(int, sys.stdin.readline().split(" "))
tree = [0]
for i in range(t):
tree.append(int(input()))
# 매번 움직였을때 안 움 직였을떄
# 1번에서 시작했을때 2번에서 시작했을때 시작은 1번
# 움직임은 30 번
# 자두나무위치, 떨어지는시간, 사용횟수
# 떨어지는 시간, 사용횟수
dp = [[0] * (w + 1) for _ in range(t + 1)]
dp[1][0], dp[1][1] = tree[1] % 2, tree[1] // 2
# 나무의 위치
for i in range(2, t+1):
# 이동 횟수
# 1번이 시작이므로 짝수번 움직 였으면 1번, 홀수면 2번임
for j in range(w+1):
x = tree[i] % 2 if j % 2 == 0 else tree[i] // 2
# dp [i][j] = i-1번 까지 j번을 사용해서 온 최댓값 + 지금 자두 얻은거
dp[i][j] = max(dp[i-1][0:j+1]) + x
print(max(dp[-1]))
자두의 이동횟수가 홀수 이고, 그때 떨어진다면 먹기 가능
반대도 동일
댓글