다이나믹프로그래밍6 [백준][다이나믹] 1890 점프 다이나믹 프로그래밍을 이용하여 풀이가 가능하다. 현재위치까지 이동가능한 경우의 수(dp[x][y])를 다음 이동가능한 위치(dp[x+move][y], dp[x][y+move])에 더하여 이동가능한 경우를 모두 더하여 준다. 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 3 3 https://www.acmicpc.net/problem/1890 2017. 6. 26. [백준][다이나믹] 11048 이동하기 이 문제는 DP로 해결 가능하다. 아래와 같이 해결이 가능하다. https://www.acmicpc.net/problem/11048 2017. 6. 26. [정올][다이나믹] 2293, 동전 1 N개의 동전의 가치를 합하여, K원을 만드는 경우를 구한다. 1, 2, 5 원의 동전을 이용하여 10원을 만드는 경우는 다음과 같다. 사용동전1 2 5 개수 1 1 1 2 1+1 2 2 3 1+1+1 1+2 2 4 1+1+1+1 1+1+2, 2+2 3 5 1+1+1+1+1 1+1+1+2, 1+2+2 5 4 5원을 만드는 경우는 위와 같다. 1원동전 사용: 1원을 5개 사용2원동전 사용: 3원을 만드는 경우에 2원을 더하여 생성5원동전 사용: 0원을 만드는 경우에 5원을 더하여 생성 https://www.acmicpc.net/problem/2293 2017. 6. 19. [백준][다이나믹] 2156 포도주 시식 포도주 시식은 포도주를 첫번째로 마시는 경우, 두번째로 마시는 경우, 마시지 않는 경우로 나누어서 생각하면 해결할 수 있다. 6개의 와인잔이 1000, 900, 2, 1, 800, 700 의 순서로 놓여져 있는 경우 다음과 같이 생각할 수 있다. 순서 1 2 3 4 5 6 첫 번째로 마시는 경우 1000 900 1002 1901 2700 2601 두 번째로 마시는 경우 0 1900 902 1003 2701 3400 마시지 않는 경우 0 1000 1900 1900 1901 2701 3번의 경우에 첫 번째로 마시는 경우는 이전에 마시지 않는 경우에서 자신을 더하는 것이다. -> 1000 + 2 = 1002두 번째로 마시는 경우는 이전에 첫번째로 마시는 경우에 자신을 더하는 것이다. -> 900 + 2 = 9.. 2017. 6. 19. [백준] 1003 피보나치 함수 일반적으로 다이나믹 프로그래밍을 이용하여 피보나치 함수를 구현하는 방법을 그대로 이용하면된다. 다른점은 0을 출력하는 것과 1을 출력하는 것을 따로 저장하여 다음 값의 호출에 0과 1을 출력하는 경우를 모두 더하여 출력하면 된다. dp[N][0] : N번째 수의 0 출력 횟수dp[N][1] : N번째 수의 1 출력 횟수 i번째 수의 0과 1출력 횟수는 다음과 같다. dp[i][0] = dp[i-2][0] + dp[i-1][0];dp[i][1] = dp[i-2][1] + dp[i-1][1]; 2017. 6. 1. [정올][다이나믹] 2000 동전교환 동전교환은 다이나믹 프로그래밍으로 해결한다. 잔돈이 n 이고, c가 코인일때 f(n) = f(n - c) + 1가 된다. 현재 잔돈에서 코인을 뺀돈의 코인개수가 있다면 거기에 +1을 하게 되면 현재의 코인개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1273&sca=3050 2016. 10. 4. 이전 1 다음
