![]()
[백준] 1, 2, 3 더하기 8 (15993번 JAVA) [접근 방법] 2차원 배열로 구성해야 한다. 수식에서 숫자가 홀수개로 구성된 것과 짝수개로 구성된 것을 따로 저장해야 한다. 정수 n이 짝수개로 구성 : dp[n][0] 정수 n이 홀수개로 구성 : dp[n][1] 와 같이 정의 하였다. 초기값은 다음과 같이 설정하였다. long[][] dp = new long[100_001][2]; // 정수 n이 짝수개로 구성 : dp[n][0] // 정수 n이 홀수개로 구성 : dp[n][1] dp[1][1] = 1; // 1 dp[2][0] = 1; // 1+1 dp[2][1] = 1; // 2 dp[3][0] = 2; // 1+2, 2+1 dp[3][1] = 2; // 1+1+1, 3 정수 n이 짝수개로..
![]()
[백준] 1, 2, 3 더하기 7 (15992번 JAVA) [접근 방법] 2차원 배열로 dp를 선언해야 한다. dp[n][m] = dp[수식의 합][수식의 수 개수] 로 정의한다. long[][] dp = new long[1_001][1_001]; dp[1][1] = 1; // 1 dp[2][1] = 1; // 2 dp[2][2] = 1; // 1+1 dp[3][1] = 1; // 3 dp[3][2] = 2; // 1+2, 2+1 dp[3][3] = 1; // 1+1+1 위와 같이 초기값을 정의한다. n이 4인 경우를 예로 들겠다. dp[4][1] = 0 4를 한개의 숫자로 구성할 수 없다. dp[4][2] = 3 4를 2개의 숫자로 구성하는 경우는 (1 + 3) , (2 + 2), (3 + 1) 과 같..
![]()
[백준] 1, 2, 3 더하기 6 (!) (15991번 JAVA) [접근 방법] 이 문제의 점화식을 찾는 것은 굉장히 어렵다. (내 기준) 주먹구구식으로 계속해서 구해보았다. dp[1] = 1; // 1 dp[2] = 2; // 1+1, 2 dp[3] = 2; // 1+1+1, 3 dp[4] = 3; // 1+1+1+1, 1+2+1, 2+2 dp[5] = 3; // 1+1+1+1+1, 1+3+1, 2+1+2 dp[6] = 6; // 1+1+1+1+1+1, 1+1+2+1+1, 1+2+2+1, 2+1+1+2, 2+2+2, 3+3 dp[7] 은 문제에서 주어진대로, 6이다. dp[7] = dp[5] + dp[3] + dp[1] 이 성립한다. dp[n] = dp[n-2] + dp[n-4] + dp[n-6] (단..
![]()
[백준] 1, 2, 3 더하기 4 (!) (15989번 JAVA) [접근 방법] 수식이 오름차순으로 정렬되어있어야 중복이 발생하지 않는다. dp[ i ] 의 수를 구하기 위해선 dp[ i - 1 ] 의 방법 에 "+1 이 더하는 행위", dp[ i - 2 ] 의 방법 에 "+2 이 더하는 행위", dp[ i - 3 ] 의 방법 에 "+3 이 더하는 행위" 가 필요하다. 2차원 배열로서 이를 구현하고자 한다. dp[ n ][ 수식의 마지막 수 ] 로 정의 한다. 예를 들어 n = 6 인 경우) dp[ 3 ][ 1 ] = 1 // (1+1+1) dp[ 3 ][ 2 ] = 1 // (1+2) dp[ 3 ][ 3 ] = 1 // (3) dp[ 4 ][ 1 ] = 1 // (1+1+1+1) dp[ 4 ][ 2 ]..
![]()
[백준] 1, 2, 3 더하기 3 (15988번 JAVA) [접근방법] 기존 [1, 2, 3 더하기] 문제와 동일하다. n의 범위가 1_000_000 까지 확장된 점이 다르다. 때문에 1,2,3으로 구성한 n의 수식의 수를 저장하는 배열인 dp의 자료형을 long으로 선언해야 한다. [JAVA 코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[..
![]()
[백준] 1, 2, 3 더하기 2 (!) (12101번 JAVA) [접근방법] 정수 n을 1,2,3의 합으로 나타내는 방법 중 사전 순으로 k 번째 오는 식을 구하는 프로그램을 작성해야 한다. 따라서, 식은 ArrayList 을 String 타입으로 선언하여 사용한다. ArrayList arr 로 선언 할때, arr[ i - 1 ] 에 있는 수식에 "+ 1"을 붙여준다. arr[ i - 2 ] 에 있는 수식에 "+ 2"을 붙여준다. arr[ i - 3 ] 에 있는 수식에 "+ 3"을 붙여준다. [JAVA 코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.Inpu..
