DP3 [Java] 백준 1890번 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 풀이 (나의 생각) 1. 칸의 개수 입력받기 2. for 문으로 배열의 값 입력받기 3. 시작점은 배열의 첫번째 값으로 잡아두고 시작 4. 오른쪽, 아래의 경우를 비교할 필요없이 모두 따져야함(모든 경우의 수를 구해야되기 때문) 5. 경우의 수의 경우 int 값으로 저장해서 총 개수를 구한다? 5번의 경우 int값으로 모든 경우의 수를 저장할 필요없이 dp배열에 값을 저장해 마지막 값을 출력하면된.. 2020. 5. 19. [Java] 백준 2293번 동전 1 (Dynamic Programming) www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1원 = 1 2원 = 1 + 1 = 2 3원 = 1 + 1 + 1 = 2 + 1 4원 = 1 + 1 + 1 + 1 = 2 + 2 5원 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 6원 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2 .... 만약 5원을 구한다고 하면 - 4원에서 +1 -> 1가지 - 3원에서 +2 -> 2가지 - 0원에서 +5 -> 1가지 => 총 4가지 N번째.. 2020. 5. 8. Dynamic Programming(동적 계획법)이란? Dynamic Programming(동적 계획법)이란? 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 구체적 알고리즘보다는 문제해결 패러다임에 가까움 cf) Divide and Conquer(분할정복)과 비슷? 분할정복 -> 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법 => 작은 문제에서 반복이 일어나는 부분이 없음 동적 계회법 -> 작은 부분 문제들의 반복(답이 바뀌지 않음)을 이용해 풀어가는 방법 차이법 => 작은 문제가 중복이 일어나는지 안일어나는지 Dynamic Programming 방법 모든 작은 문제들은 한번만 푼다 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문.. 2020. 4. 28. 이전 1 다음