study

문제 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 - 같은 숫자가 2개 연속으로 나오면 안되기 때문에 dp 배열을 2차원 배열로 만든다 - n을 만들 수 있는 식 중 1로 끝나는 식은 dp[n][1]에, 2로 끝나는 식은 dp[n][2]에, 3으로 끝나는 식은 dp[n][3]에 담는다 - dp[n][1]에는 i-1을 만들수 있는 식 중 2로 끝나는식, 3으로 끝나는 식 개수를 넣는다 - dp[n][2]에는 i-2를 만들수 있는 식 중 1로 끝나는식, 3으로 끝나는 식 개수를 넣는다 ..

문제 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해결 - 11052 카드 구매하기 문제와 비슷하다 https://broship.tistory.com/220 - 다만 n개의 카드 구매를 위해 최대값을 구하는게 아니라 최소값을 구하면 된다 import java.util.Scanner; public class B16194 { public static void main(String[] args) { Scanner sc = new Scanner(S..

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해결 - dp 배열을 만들고 dp[1] : 카드 1개 사는 최대값 dp[2] : 카드 2개 사는 최대값 .... dp[n] : 카드 n개 사는 최대값을 넣는다 - dp[i]를 구하기 위해선 또다시 반복문을 돌며 모든 dp[i-j] + dp[j]의 값중 가장 큰 값을 dp[i]에 넣는다 i가 5일때 dp[5] : 5장 카드 살때 dp[5-1] + dp[1] : 4장 카드 구매하는 최대값 + 1장 ..

문제 문제해결 - 정수 1을 1, 2, 3의 합으로 나타내는 방법은 1 총 1개 - 정수 2를 1, 2, 3의 합으로 나타내는 방법은 1 + 1 2 총 2개 - 정수 3을 1, 2, 3의 합으로 나타내는 방법은 1 + 1 + 1 1 + 2 2 + 1 3 총 4개 - 그렇다면 정수 4를 1, 2, 3의 합으로 나타내는 방법은 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 (4) 2 + 1 + 1 2 + 2 (2) 3 + 1 (1) 이렇게 4 + 2 + 1 = 7가지다, 잘 보면 1 + 우측에는 3을 나타내는 경우의 수(4) 2 + 우측에는 2를 나타내는 경우의 수(2) 3 + 우측에는 1을 나타내는 경우의 수(1) 즉 3의 경우의수 + 2의 경우의 수 + 1의 경우의 수인것을 볼수..

문제 문제해결 - 1*2 와 2*1의 타일로만 채우는 문제에서는 dp[i-1] 에 세로 타일 하나 추가한 경우의 수 + dp[i-2] 에 가로 타일 두개 추가한 경우의 수를 구하면 되었다 - 이 문제의 경우 2*2 타일이 있으므로 dp[i-1] 에 세로 타일 하나 추가한 경우의 수 + dp[i-2] 에 가로 타일 두개 추가한 경우의 수 + dp[i-2]에 2*2 타일 하나 추가한 경우의 수 - dp[i] = dp[i-1] + dp[i-2] + dp[i-2] - dp[i] = dp[i-1] + dp[i-2] * 2 - 피보나치 수열 구하는 방법이랑 똑같이 하되 점화식만 바꿔주면 된다 import java.util.Scanner; //dp[i] = dp[i-1] + dp[i-2] * 2 public clas..

문제 문제해결 - 1*2와 2*1의 직사각형으로 2*n을 만들 수 있는 경우의 수는 1, 2, 3, 5, 8.... - 2*3의 직사각형을 만들기 위해선 모든 2*2 직사각형에(dp[i-1]) 세로 타일 하나 추가 한 경우의 수 + 모든 2*1 직사각형에(dp[i-2]) 가로 타일 두개 추가한 경우의 수 즉 dp[i] = dp[i-1] + dp[i-2] - 2*0을 제외하고 보면 피보나치 수열임을 알수있다 - 2*0일 경우를 임의로 1로 설정하면 피보나치 수열 해결 방식으로 문제 풀이가 가능하다 - 피보나치 수열의 경우 n이 증가함에 따라 값이 기하급수적으로 커지므로 10007이라는 값을 항상 나눠줘서 overflow가 안나게 한다 import java.util.Scanner; //피보나치 수열 publ..

문제 문제해결 - dp 배열을 만들고 x+1까지 돌면서 i를 1로 만들기 위한 최소 연산 횟수를 담아둔다 - f(x) = min(f(x-1), f(x/2), f(x/3)) + 1 - 1은 연산횟수가 0이므로 2부터 시작한다 - -1연산, /2연산, /3연산 순서대로 더 작은 값이 되므로 /2연산이랑 /3연산은 나누어 떨어질때만 포함시키며 가장 횟수가 적은 값을 dp[i]에 담는다 - dp[x]가 x를 1로 만들기 위한 최소 연산 횟수가 된다 import java.util.Scanner; public class B1463 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); //..

문제 문제해결 1. 주어진 배열을 뒤집으면 최장 증가 부분 수열 문제 푸는 방식으로 풀수있다 2. 숫자가 하나일때 최장 길이는 1이므로 dp 배열을 1로 초기화 한다 3. 반복문을 돌며 arr[j]

문제 문제해결 1. 금의 위치를 arr 배열에 담는다 2. 각 위치의 최고값을 기록할 dp 배열을 만든다, 맨 좌측은 더할 값이 없으므로 arr과 똑같이 초기화 한다 3. 점화식: dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]) - 이때 행이 아닌 열 순서대로 계산해야 하기 때문에 상위 반복문을 m만큼, 하위 반복문을 n만큼 돈다 - 맨 위 행일때랑 맨 아래 행일때는 i-1, i+1이 성립 안되기 때문에 if문으로 검사해준다 4. 맨 우측에 있는 열 중 가장 큰 값이 정답 import java.util.Scanner; public class Ex05_금광 { public static void main(String[] args) { S..

문제 해설 문제해결 1. 각 화폐 단위를 배열로 받는다 (int[] money) 2. 0~m원까지 가지고 있는 화폐로 만들 수 있는 최소 개수를 구하기 위한 dp 배열을 만든다 3. dp 배열의 0원은 0원으로 만들수있으므로(?) 0으로, 나머지는 10001(나올수 없는 최대값)로 초기화 한다 4. 2중 반복문을 돌며 각 화폐마다(mon) i-mon을 만들 수 있으면(dp[i-mon]!=10001) dp[i]와 dp[i-mon]+1의 최소값을 dp[i]에 넣는다 5. 마지막 dp[m]이 10001일 경우 구할 수 없는 경우므로 -1을 그 외는 dp[m]을 출력하면 된다 import java.util.Scanner; public class Ex04_효율적인화폐구성 { public static void ma..