[백준(baekjoon) 2156] 포도주 시식 문제 백준 2156 n(1…10,000)개의 포도주가 있고 각 값이 주어진다. 포도주 선택 시 한잔을 모두 마셔야 하고, 연속으로 최대 2잔 마실 수 있을 때 최대 값을 구하라. 예시 : n = 6 { 6, 10, 13, 9, 8, 1 } => 정답은 1, 2, 4, 5{O, O, X, O, O, X}를 선택 할 때 33으로 최대다. 주의 : 각 포도잔의 값은 음이 아닌 정수이다. 해결 DP로 풀어야 한다는 전제하에 진행하였다. 난 DP 연습을 하고 있기 때문에. 단순하게 O, X 형식으로 하면 2^10000으로 2초를 훌쩍 넘긴다..! 그 다음에 여러 시도를 해봤었는데, (아래와 같은 것들?) 모두 시간초과가 떴다.. 3개씩 묶으면 그 안에 무조건 X하나..

[백준(baekjoon) 2193] 이친 수 문제 백준 2193 n(1…90)이 주어질 때, 길이가 n인 이친 수의 개수를 구하는 문제 이친 수 : 0으로 시작하지 않고, 11을 부문 문자열로 가지지 않는 이진 수 예시 : 1, 10, 101, 10101 해결 길이가 n인 이친 수는 길이가 n-1인 수의 끝자리를 기준으로 구할 수 있다. n-1의 끝자리가 0일 때 : 뒤에 0과 1을 붙일 수 있다. n-1의 끝자리가 1일 때 : 뒤에 0만 붙일 수 있다. (11은 불가하기 때문) 즉, 끝자리가 1, 0인 경우를 각각 저장해두고 이를 활용해 구하면 된다. n 예시 이친 수의 총 개수 끝자리가 0인 개수 끝자리가 1인 개수 1 1 1 0 1 2 10 1 1 0 3 100 101 2 1 1 4 1000 100..

문제 백준 10844 n(1…100)이 주어질 때, 길이가 n인 계단 수를 구하는 문제 계단 수 : 인접한 수의 차이가 1인 수 예시 : 12321, 3456, 101 주의 : 0으로 시작하는 수는 없다. 해결 계단 수는 끝자리를 기준으로 하기 때문에, *끝의 자리가 0...9인 경우를 각각 따져보면 된다. N이 100이하이기 때문에, 100 * 10을 해도 1초가 넘지 않으므로 시간초과가 되지 않는다. N = 1의 경우, 0을 제외한 1...9까지가 가능하다. 이 경우는 무조건 초기화 해준다. (N > 1)을 만족하는 길이가 N인 계단 수의 규칙은 다음과 같다. 끝자리가 0 인 계단 수 : 직전 값이 1일 경우에만 가능 끝자리가 9 인 계단 수 : 직전 값이 8일 경우에만 가능 끝자리가 1~8 인 계단..

[백준(baekjoon) 11057] 오르막 수 문제 백준 11057 n이 주어질 때, n개의 자리인 오름차순의 개수를 구하는 문제 예시 : 2232, 1234, 4311 주의 : 인접한 수가 같아도 된다. 해결 오름차순의 조건이 끝의 자리보다 작거나 같은 수이기 때문에, 끝의 자리가 0..9인 개수를 모두 따져보면 된다. 그 결과는 다음과 같다. 해당 표는 int[][] count = new int[n][10]라는 2차원 배열로 나타낼 수 있다. count[n][i]는 n번째에 i로 끝나는 수들의 총 개수이고, count[n][i] = count[n-1][i] + count[n][i-1]라는 규칙을 가지고 있다. 저는 왜 그런지 궁금해하면서 원리를 어떻게든 파악하는 편이라, 여기서 부터 너무 복잡하게 ..

[백준(baekjoon) 11052] 붕어빵 판매하기 문제 백준 11052 n개의 붕어빵이 남았고, 이 중 i개로 이루어진 세트의 가격을 Pi라고 한다. 세트 메뉴의 가격이 주어졌을 때, 최대 수익을 구하는 프로그램을 작성하시오. 예시 n = 4; P1 = 1, P2 = 5, P3 = 6, P4 = 7; ANSWER : P2, P2 = 5 + 5 = 10; 해결 1, 2, 3의 더하기 문제와 흡사하다. n을 이룰 수 있는 조합을 찾아 각각의 Pi를 모두 더한 값 중 최대 값을 찾는 문제이다. 다른 점은 조합이 1, 2, 3만으로 이루어지지 않는다는 것. 결론을 먼저 이야기 한다면, 두 원소의 합이 n이 되는 순서를 고려하지 않은 조합을 찾고, 각 max 가격을 찾아 더하면 된다. ‘두 원소의 합’인 이유..

[백준(baekjoon) 9095] 1, 2, 3 더하기 문제 백준 9095 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 n = 4; 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1 input 첫째줄 : T(테스트 개수) 그 다음 줄 부터 : n(11보다 작은 자연수, T번 반복됨) 해결 우리가 찾고자 하는 수는 1, 2, 3의 조합이다. 즉, 쉽게 생각해 1, 2, 3으로 각각 시작하는 경우의 수를 모두 찾아보면 답이 나온다. 예를 들어 n = 6라고 할 때, 1, 2, 3 을 기준으로 생각해 본다면, 6 = 1 + 5, 6 = 2 + 4, 6 = 3 + 3로 나타낼 수 있다. 즉 n = 6의 경우,..