Algorithm/Dynamic Programming
[Java] 백준 #1463 1로 만들기
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산 세 가지를 적절히 사용해서 정수 N을 1로 만든다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 연산 사용 횟수의 최솟값 구하기 💡 알고리즘 다이나믹 프로그래밍 💡 접근 RGB거리처럼 모든 케이스의 계산횟수가 동일한 문제가 아니므로, 배열만으로는 해결하기 어려울 것 같다. → 재귀함수를 작성하고, 전역변수를 통해 최솟값을 관리하자. 💡 코드 package DP; import java.io.BufferedReader; imp..
[Algorithm/Java] 다이나믹 프로그래밍 복습
DP문제 해결 과정 = 규칙을 찾아 점화식 세우기 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 처음엔 감이 안잡히므로.. 그냥 몇문제 답을 보고 시작하는게 효율적이다. 💡 ex1. RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 주어진 비용으로 N개의 집을 빨, 초, 파로 칠하는데 N번 집은 N-1, N+1번 집과 색이 같으면 안된다 집을 칠하는 최소..
[Python] 백준 #11052 카드 구매하기
11052번: 카드 구매하기 (acmicpc.net) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [알고리즘] DP [접근 방법] N개의 카드 팩이 있고, N개의 카드를 구매하는 상황. D[i] = 카드 i개를 구매하는 최대 비용, dp[k] = 카드 k개가 들어있는 카드팩의 가격 일 때, 카드 i개를 구매하는 최대 비용의 경우의 수는 D[1] + dp[i - 1] D[2] + dp[i - 1] D[3] + dp[i - 3] ... D[i] + dp[0] [코드] 1 2 3 4 5 6 7 8 9 10 11 N = ..
[Python] 백준 #1932 정수 삼각형
1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [알고리즘] DP [접근 방법] 각 층의 양 끝에 있는 수 → 바로 위의 수와 그대로 더해진다 중간에 있는 수 → 바로 위의 두 수 중, 더 큰 수와 더해진다 → 이 방법으로 맨 아래층까지 더하면, n개의 경우의수가 구해지고(n = 층수) , 그 중 가장 큰 수를 출력한다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n = int(input()) D = [] for _ in range(n): D.append(list(map(int, input().split()..
[Python] 백준 #1149 RGB거리
1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [알고리즘] DP [접근 방법] 1. 점화식 세우기 * i-1번째 집과 i번째 집의 관계 → 조건은 서로 다른 색 * 최소비용 구하기 →min으로 비교 2. 경우의수 생각 * i번째 집이 R, G, B인 경우 3가지 [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 N = int(input()) cost = [] for i in range(N) : cost.append(list(m..