38661 백준(BOJ) 3866 풍선 수집(Python) 2차원 DP 문제. 가로 길이는 전체 풍선의 개수, 세로 길이는 현재 로봇에 달려 있는 풍선의 개수로 2차원 DP 리스트를 설정했다. 당연히 풍선은 빨리 떨어지는 순으로 받아줘야 하고, 첫 풍선은 선택지 없이 집에서 출발해 받아줘야 한다. 그 다음부터 떨어지는 풍선에 대해서는 2가지의 선택지가 존재한다. 풍선을 집에 두고 받을 것인지, 그냥 받으러 갈 것인지. 이를 DP에 적용해주면 된다. i가 전체 풍선의 개수만큼의 반복문의 인자, j가 로봇에 달릴 수 있는 풍선의 개수만큼의 반복문의 인자라고 하면 첫 번째 경우 풍선의 개수가 1개로 변하는 과정이므로 dp[1][i+1]=min(dp[1][i+1],dp[j][i]+p+x)라는 점화식을 세울 수 있다. 두 번째 경우 풍선의 개수가 (현재 풍선의 개수).. 2022. 7. 8. 이전 1 다음
