DP

[JAVA] 백준 1890번 : 점프

1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 NXN 게임판에 수가 적혀져 있다. 게임의 목표 : 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것 각 칸에 적혀 있는 수 : 현재 칸에서 갈 수 있는 거리 -> 반드시 오른쪽이나 아래로 가야함. -> 한 번 점프를 할 때, 방향을 바꾸면 안됨. -> 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두가지 경우만 존재. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 ..

[JAVA] 백준 14501번 : 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 - N+1일째 되는 날 퇴사 - 남은 N일 동안 최대한 많은 상담을 함 - 각각의 상담은 상담을 완료하는데 걸리는 기간 : Ti - 상담을 했을 때 받을 수 있는 금액 : Pi 이때 얻을 수 있는 최대 수익을 구하는 프로그램 - N = 7인 경우에 다음과 같은 상담 일정표 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게..

[JAVA] 백준 1932번 : 정수 삼각형

1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. - 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 - 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택가능 - 삼각형의 크기는 1 이상 500 이하이다. - 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9..

[JAVA] 백준 2293번 : 동전 1

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 - n가지 종류의 동전이 주어지고, 각각의 동전이 나타내는 가치는 다를 때, 그 가치의 합이 k원이 되도록 하는 그 경우의 수를 구하는 프로그램. - 각각의 동전은 몇 개라도 사용가능 - 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우로 침. 입력 - 첫째 줄에 n, k가 주어짐. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) - 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. (100,000보다 작거나 같은 자연수) 출력 첫째 줄에 경..

[JAVA] 백준 9461번 : 파도반 수열

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그..

[JAVA] 백준 11726번 : 2Xn 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 - 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력. 풀이 처음부터 노가다로 구해보니까 점화식이 나왔다. DP[N] = DP[N-1]+DP[N-2] 임을 확인할 수 있다.. public class bj11726 { public static void main(String[] args) { //..

[JAVA] 백준 2225번 : 합분해

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 - 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램 - 덧셈의 순서가 바뀐 경우 다른 경우로 셈(1+2와 2+1은 다른경우) - 한 개의 수를 여러번 쓸 수 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200) 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력. 풀이 만약 입력에 5, 3가 주어졌다고 가정했을 때, 생각할 수 있는 경우의 수는 아래와 같다. 5 = 0 (2번 더해서 0이 되는 경우)+ 5 5 = 1 (2번 더해서 1이 되는 경우)+ 4 5 = 2 (2번 더해서 2이 되는 경우)+..

[Algorithm] DP(Dynamic Programming) / 동적 프로그래밍이란?

DP(Dynamic Programming) 이란? 동적 프로그래밍이라고도 불리는 동적 계획법은 분할 정복 기법과 굉장히 유사하다. 분할 정복 기법이란, 알고리즘을 짤 때 큰 문제를 한 번에 해결하지 않고 작은 여러 개의 문제로 나누어서 푸는 기법이다. 이렇게 풀다보면 같은 문제를 반복적으로 풀게되는데, 이를 매번 재계산하지 않고, 값을 저장해두었다가 재사용하는 기법이 바로 동적 계획법이다. 동적 계획법의 종류 Top-down - 하향식 계산법 - 큰문제부터 시작해 작은 문제로 분할 - 메모제이션 : 동일한 계산을 반복해야 할 경우, 한 번 계산한 결과를 메모리에 저장해두었다가 꺼내씀으롰 중복계산방지를 할 수 있게 하는 기법으로, 동적 계획법의 핵심 기술이다. 즉, 메모리라는 공간비용을 늘림으로써 계산에 ..