파이문

2293. 동전 1(https://www.acmicpc.net/problem/2293) 동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS) 구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다. 예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다. 유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ..

11053. 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053) 유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS) 일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다. 동영상 설명이 잘 되어 있어서 링..

2579. 계단 오르기(https://www.acmicpc.net/problem/2579) 문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.) 계단이 4개 있을 때로 문제를 늘리면 1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4]) 왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보..

1149. RGB 거리(https://www.acmicpc.net/problem/1149) dp[i][j]라는 배열을 만들어서, i는 i번째 집이고 j는 색을 의미하게 하였다. 그 값으로는 i번째 집이 j의 색을 가질 때, 가질 수 있는 최소 값을 넣었다. 정리하자면 i번째 집을 j색으로 칠할 때 + (i-1번째 집이 j색이 아닌 다른색으로 칠했던 경우의 최소 값) 인 것이다. public void problem1149(int houseCount, ArrayList n) { int[][] dp = new int[houseCount][3]; dp[0][0] = n.get(0); dp[0][1] = n.get(1); dp[0][2] = n.get(2); for (int i=1; i

1463. 1로 만들기(https://www.acmicpc.net/problem/1463) 동전 경우의 수 구하는 문제랑 비슷하다. 다만 앞에서 하는게 아니라 뒤에서 풀어야 풀린다. (다른 방법은 잘 모르겠음) 예를 들어서 8이 주어지면 8에서 만들 수 있는 수는 8-1, 8/2 두 가지이다. 이 때 나오는 수인 7, 4를 인덱스로 가지는 dp 에 1을 넣어준다. 이것이 맨 처음에 1을 넣어주는 부분이다. (초기화를 n-1하는 이유는 어떤 수 n에서 1을 만드는 가장 최댓값이 n-1이기 때문이다.) 그리고 그 다음 7부터 거꾸로 dp를 만들어 주면 된다. (인덱스) i에서 i/2, i/3, i-1에 i를 만들수 있는 값 + 1과 해당 값의 최솟값만 갱신해 주고, 목표가 1을 만드는 것이기 때문에 dp의 ..

1003. 피보나치 함수(https://www.acmicpc.net/problem/1003) 숫자를 입력받아, (피보나치 계산으로) 1과 0을 얼마나 호출하는지를 출력하는 문제이다. 케이스 범위에 따라, 이전 계산 값을 그대로 사용할 수 있게 보완하면 더 좋을듯 public void problem1003(int n) { if (n == 0) { System.out.println("1 0"); } else if (n == 1) { System.out.println("0 1"); } else if (n == 2) { System.out.println("1 1"); } else { int[][] dp = new int[n + 1][2]; dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1..