oiehso0

https://www.acmicpc.net/problem/1699

풀이

dp를 이용해서 풀기로 한다. N의 범위가 100,000이므로 100,000의 제곱근의 반올림 수인 317개의 배열을 선언해 주기로한다.

dp[100001] = { 0 };

arr[317]  = { 0 };

그리고 dp 배열을 모두 -1로 초기화 해주기로 한다. 그 이유는 0과 -1의 구분을 짓기 위해서인데 초기화 했던 -1로 계속 값이 남아 있는 경우는 이전까지의 

제곱수로 만들수 없다는 것을 의미하게끔 하기 위해 

또, dp[0]값과 초기화 값이 0으로 동일하다면 min함수를 쓰기가 어려워지기 때문에 if(dp == -1) 조건을 두어

사전에 거르기 위함이다.

dp[0] = 0개

dp[1] =   1개    /     1^2 

dp[2] =  2개    /   1^2 + 1^2 

dp[3] =   3개    /    1^2 + 1^2 + 1^2

dp[4] =    1개    /    min(dp[3] + 1개(1^2) or  dp[0] + 1개(2^2))

dp[5] =    2개   /    dp[4] + 1개(1^2)    

dp[6] =    3개    /    dp[5] + 1개(1^2)

dp[7] =     4개    /    dp[6] + 1개(1^2)

dp[8] =    2개    /    min(dp[7]    or   dp[4]  + 1개(2^2))

.

.

.

이런식으로 비교해주면서 최소값을 저장해 나가면 된다.

https://www.acmicpc.net/problem/11048

풀이

NxM의 배열을 받고 (1,1)부터 출발해서 (N,M)에 도착했을때 최대가 될 수 있게 사탕을 챙겨야한다.

이동할 수 있는 방법은     →    /    ↓    /    ↘︎    이렇게 세가지 방법이 있다. 하지만 여기서  사탕은 0보다 같거나 크기 때문에   ↘︎ 으로 갈때 ↓ 와 → or → 와 ↓ 조합으로 이동해도

적어도 손해는 없기 때문에 대각선 이동은 고려하지 않기로한다. 

(i,j) 까지 왔을때  최대값을 구하기 위해서는 (1,1)에서부터 끊임없이 비교를 하며 최대값을 채택해 (i,j)까지 와야한다.

예를 들어 (3,3)좌표에서 최대값을 가지고 싶을때  3,4번 화살표와 같이

(2,3)에서 와야하는지 (3,2)에서 와야하는지 비교가 필요하다.

즉, i 와 j 가 1 이 아닌 경우

arr[i][j] += max(arr[i][j-1], arr[i-1][j]); 와 같은 식이 성립한다.

그러면 나머지 두가지 경우가 남는다.

1. j == 1 인 경우

위 그림의 1번 화살표와 같이 비교할 필요없이 위에서 아래로 누적해주며 내려오면 된다.

if(j == 1) arr[i][j] += arr[i-1][j]; 

2. i == 1 인 경우

그림의 2번 화살표와 같이 오른쪽으로 누적해주기만 하면 되므로

if(i == 1) arr[i][j] += arr[i][j-1]; 과 같은 식이 성립한다. 

https://www.acmicpc.net/problem/2294

풀이

첫번째 줄에 n,k를 입력한다. n은 서로 다른 값의 동전의 종류이고 그 동전들을 적당히 이용해서 그 가치의 합을 k로 만들어야할때, 동전의 개수가 최소가 될때를 구해야한다.

단, 불가능한 경우에는 -1을 출력하기로 한다.

arr[101]을 0으로 초기화해주고 

dp[100001] 을 memset(dp, -1, sizeof(dp));를 이용해서 -1로 초기화 해주기로 한다. 

dp[0]은 0 으로 초기화

동전1 문제의 풀이법을 변형해서 dp[i] = dp[i - arr[j]] + 1; 을 사용하여 동전이 사용될 때마다 +1 을 누적하여 dp에 담기로 한다.

if( i >= arr[j] && dp[i - arr[j]] != -1)의 조건을 주어서 arr[j] 동전이 i의 값을 넘지 않고 dp[i - arr[j]]이 이전의 동전들의 값으로 만들 수 있는 경우만 생각하면 된다.

하지만 dp[i] == -1 인 경우는 dp[i]가 처음으로 -1에서 값을 가지는 순간이므로 min함수로 비교를 하지않고 바로 dp[i] = dp[i - arr[j]] +1; 이 된다.  이 다음부터는

dp[i] = min(dp[i], dp[i - arr[j]] + 1);로 매번 비교를 해주어야 한다.