백준

[백준] 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..

[백준] 1, 2, 3 더하기 5 (★) (15990번 JAVA) / 400 - 다이나믹 프로그래밍 1 [접근방법] ** [1, 2, 3 더하기] 시리즈에서 중요한 것은 N을 만들기 위해 사용할 수 있는 숫자는 1 , 2 , 3 뿐이라는 것이다. 이 당연한 말이 뭐가 중요한가 싶겠지만, 사용 가능한 숫자가 1, 2, 3 뿐이라는 것은 dp[N] 에 영향을 줄 수 있는 원소들은 dp[N - 1] , dp[N - 2], dp[N - 3] 뿐이라는 것이다.따라서 점화식 dp[N]은 dp[N - 1] , dp[N - 2], dp[N - 3]을 이용하여 만들어진다. N을 만들 수 있는 방법 수를 저장한 배열인 dp[]는 2차원 배열로 구성된다. dp[i][1] : 합이 i 가 되는 수식이 '1' 로 끝나는 경우의..

[백준] 400 - 다이나믹 프로그래밍 1 : 카드 구매하기 2 (16194번 JAVA) [접근 방법] 기본적인 풀이방법은 [11052 카드 구매하기]와 동일하다. * 추가 해야 할 부분은 카드 i 개의 최솟값을 저장하는 배열인 dp에 초기값을 부여해주어야 한다. 그 이유는 초기값을 부여 해주지 않는 경우, Math.min()을 활용한 비교 과정을 통해 모든 값이 0 이 될 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.String..