목록5557 (1)

-

DP :: 백준 :: 1학년 :: 5557

1학년 5557https://www.acmicpc.net/problem/5557 [문제 풀이]눈여겨 볼 점은 계산을 하다보면 범위가 int형 범위를 넘어갈 수도 있다는 점.상근이가 아는 수는 다행히 0부터 20까지라는 점이다. 1. 숫자의 개수 N을 입력받고 2. 다음 줄에 나오는 N개의 숫자를 long형 ar[]배열에 집어넣는다. 3. 2차원배열 dp[N+1][21]를 생성한다. 어떻게 풀어나갈 생각이냐면.... dp[i][j]를 'i번째 수 까지 계산을 했을 때 j를 만들 수 있는 경우의 수'로 생각한다. 예를들어, dp[1][8] = 1 (8 = 8) dp[2][5] = 1 (8 - 3 = 5) dp[2][11] = 1 (8 + 3 = 11) 이다. 4. dp[i-1][]와 dp[i][]와의 관계를..
알고리즘/DP 2016. 11. 4. 01:13
Prev 1 Next