https://www.acmicpc.net/problem/2839 풀이 규칙을 찾아서 풀었다.dp[12]dp[14]dp[16]dp[18]dp[20]dp[22]dp[24]dp[26]dp[28]dp[30]4444466666 12번째 idx부터 idx+=2를 5번 할때까지 4봉지이고, 이후 짝수 5개는 설탕봉지 2개가 증가한 6봉지이다. 4봉지 .. 6봉지 .. 8봉지 .. 씩 5번dp[17]dp[19]dp[21]dp[23]dp[25]dp[27]dp[29]dp[31]dp[33]dp[35]5555577777 17번째 idx부터 idx+=2를 5번 할때까지 5봉지이고, 이후 홀수 5개는 설탕보지 2개가 증가한 7봉지이다.5봉지 .. 7봉지 .. 9봉지 .. 씩 5번 dp[4] 와 dp[7]은 유일하게 3봉지/5봉..

11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net package 백준renew; import java.io.*; import java.util.*; public class 실버2_11055_가장큰증가하는부분수열 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buff..

11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net package 백준renew; import java.io.*; import java.util.*; public class 실버2_117722_가장긴감소하는부분수열 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net package 백준renew; import java.io.*; import java.util.*; public class 실버2_11053_가장긴증가하는부분수열 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System...

11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 모듈러 처럼 10007로 계속 나눠줘야 하고, 규칙 찾기가 어려웠따 .. 근데 열심히 계산하다보니 어? 하는 순간에 발견한 규칙으로 풀었다. 누적합의 총합 = 다음 idx의 오르막 수의 합 package 백준renew; import java.io.*; import java.util.*; public class 실버1_11057_오르막수 { public static void main(String[] args) throws E..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net package 백준renew; import java.io.*; public class 실버3_11726_2xn타일링 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));..

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 후기 문제집: 좋은 DP문제들 (khanjhy) www.acmicpc.net 최근 DP 복습을 위해 DP문제들 모아놓은 백준 문제집을 애용중이다! package 백준renew; import java.io.*; import java.util.*; public class 실버3_9095_123더하기 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..

17202번: 핸드폰 번호 궁합 어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다. 핸드폰 번호 궁합을 보기 위해서는 www.acmicpc.net 후기 ㅋㅋ 규칙 찾아서 풀어보려고 했는데 2시간 동안 결국 규칙을 못찾았답니다. 규칙을 찾는다면 어떻게 풀어야겠다~ 는 틀은 나왔는데, 숫자가 몇개씩 사용되는지 노가다를 해도 도저히 안풀려서 ^^; 그냥 문자열을 활용해서 풀었다. package 백준renew; import java.io.*; import java.util.*; public class 브론즈1_17202_핸드폰번호궁합 { public static void main(String[] args) thro..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1463: 1로 만들기를 DP를 사용해서 다시 풀어봤다. 풀이 재귀함수는 Top-down 방식이고, DP는 Bottom-Up 방식이다. 점화식(작은 문제를 해결해서 큰 문제를 해결하는 방법)을 활용한 다이나믹 프로그래밍 방식이다. 이 방식은 부분 규칙을 활용해서 전체 문제를 푸는 방식인데, DP로 문제를 풀려면 DP인지 아닌지 확인하는 것이 중요하다고 한다. 1을 만들어야하니까, 0에서 부터 확인을 한다면, dp[1] = 0; 1은 0이다. 왜냐면 2로 나눠지지도 않고, 3으로 나눠지지도 않기 때문. 그리고 마지막 1이 되면 끝나기 때문에 0. 그럼 이 다음 어떻게 해야할까?..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net package 백준renew; import java.io.*; import java.util.*; public class 실버3_1463_1로만들기 { static int N; static int arr[]; static boolean visited[]; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputSt..