본문 바로가기

동적계획법21

[Java] 백준 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 설명 크기가 N인 정수 삼각형 꼭대기에서 아래로 내려오면서 선택된 수의 합이 최대가 되는 경로 구하기 아래층 수는 현재층 대각선 왼쪽, 오른쪽만 선택 가능 삼각형의 크기는 1 이상 500 이하, 수는 0 이상 9999 이하의 정수 꼭 문제에 나와있는 그림처럼 정수 삼각형을 생각할 필요 없다. 우선 DP[N+1][N+1] (dp [][] = 각 자리의 수) 배.. 2020. 5. 16.
[Java] 백준 14501 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 설명 N일 동안 상담을 완료해서 받을 수 있는 최대 수익 구하기. Ti = 상담하는데 걸리는 기간 Pi = 상담했을 때 받을 수 있는 금액 상담 중인 기간에는 다른 상담을 할 수 없다. 마지막 날부터 첫째 날까지 뒤에서 앞으로 거꾸로 생각하면 더 쉽게 풀 수 있는 문제 같다. dp [i] = i일부터 퇴사 날까지 얻을 수 있는 최대 이익이라고 하자. 상담일로부터 상담을 완료받기까지 걸리는 시간을 계산해 조건 (i + T [i] < N+1)을 만족시키는지 검사한다. N+1인 이유는 상담이 걸리는 시간이 상담을 시작한 날을 포함하기.. 2020. 5. 14.
[Java] 백준 2225번 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 0~N까지 정수에서 K를 더해 합이 N이 되는 경우의 수를 구하는 것. 덧셈의 순서가 바뀐 경우(1+2와 2+1)는 다른 경우이다. 하나의 수는 중복 가능하다. -> 즉, (1+1+0, 1+0+1, 0+1+1) 모두 다른 경우 처음 문제를 접했을때 점화식이 바로 생각나지 않았다. 2차 배열을 생각하여 표를 그려 생각해보면 쉽다. N=3, K=3인 경우를 생각해보자. 0~3까지 정수 중 3개를 더해 합이 3가 되는 경우의 수를 구하는 것이다. DP[N][K] 이중배열은 경우의 수를 의미한다. 표를 그려보면 다음과 .. 2020. 5. 8.
[Java] 백준 2293번 동전1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 n가지 종류의 동전을 사용해서 K원을 만들 수 있는 경우이 수 구하기 (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 동전 사용 갯수는 상관없다. 동전의 구성이 같으면 순서 상관없이 같은 경우 -> 2원+1원과 1원+2원은 같은 경우이다. 동전1(1원)로 k(1~10)원을 만들 수있는 경우의 수는 자기 자신으로 각 한 가지이다. 1원 2원 3원 4원 5원 6원 7원 8원 9원 10원.. 2020. 5. 7.
[Java] 백준 9461번 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 규칙만 찾으면 쉽게 풀 수 있는 문제이다. P(1)부터 P(10)까지의 값은 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 여기서 내가 발견한 규칙은 각 n자리의 값을 dp [n]이라고 했을 때 dp[n]= dp[n-3] + dp[n-2]이다. 배열은 0부터 시작이므로 dp[0]=0으로 초기화시켜주고 dp[1]=1,dp[2]=1로 초기화 시키면 n>=3부터 적용시킬 수 있다. 또 다른 두.. 2020. 5. 6.
[Java] 백준 11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 그림을 그려서 문제를 이해해보면 쉽다. N=1 일 때, 2x1의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 하나이다. N=2 일때, 2x2의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 두 개와 2x1의 타일 두 개로 채울 수 있으므로 두 가지이다. N=3 일 때, 2x3의 직사각형을 타일로 채우는 방법의 수는 2x1의 타일 세 개와 2x1의 타일 두 개, 2x1타일 하나씩 두 가지 경우로 채울 수 있.. 2020. 5. 6.

티스토리툴바