Storage Gonie

파도반 수열 문제 - https://www.acmicpc.net/problem/9461 문제요약 삼각형으로 나선을 만드는데 변의 길이가 1인 정삼각형에서 시작한다. 다음 삼각형은 지금까지 만들어진 나선에서 가장 긴 변에 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1) ~ P(12) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 P(N)의 값을 출력하는 프로그램을 작성해라. 해결 방법 1. D[i] 정의 생략. 2. 점화식 세우기 방법1. 직감으로 본뒤 점화식이 옳은지 확인 P(12) = 12, P(11) = 9, P(7) = 3 에서 볼 수 있듯이 P(12) = P(11) + P(7) 이다. 또한, 이러한 패턴을 다른곳에서도 보여준다. 따라서,..

타일 채우기 문제 - https://www.acmicpc.net/problem/2133 문제요약 3 x N의 타일을 1 x2, 2 x 1 타일로 채우는 방법의 수 구하기 해결 방법 1. D[i] 정의 D[N] = "3 x i 를 채우는 방법의 수" 2. 점화식 세우기 N번째에 올 수 있는 경우의 수를 모두 조사해 봐야 한다. 길이가 2인경우, 4인경우. 6인경우, ... 모두 다른 경우의 수이다. ... ... 따라서 D[i] = 3D[i-2] + 2D[i-4] + 2D[i-6] + ... (i-k >= 0 일 동안) 이다. 타일의 모양상 i가 홀수일 때는 채우지 못하므로 i는 짝수이어야 한다. (1)시간복잡도 = for 문의 반복 횟수 (2) 구현 -> 'for문을 이용한 반복문'으로 구현 #inclu..

제곱수의 합 문제 - 백준 No.9095 : 1, 2, 3 더하기 문제와 비슷함 - https://www.acmicpc.net/problem/1699 문제요약 어떤 자연수 N이 주어지면 이를 N보다 작은 제곱수의 합으로 나타내는 데, 이때의 항의 최소개수를 구해라. 해결 방법 1. D[i] 정의 D[N] = "자연수 N을 제곱수의 합으로 나타내는데 이때의 항의 최소개수" 2. 점화식 세우기 정수 N이 주어지면 앞에 어떤 조합들이 오고 맨 뒤에 i^2이 온다고 해보자. O + O + O + ... + i^2 = N 이 된다. 여기서 i^2를 제외시킨 앞의 나머지 항들에 대해서만 생각해보면 D[N] = min(D[N - i^2] + 1) 가 된다. i^2 이 1^2, 2^2, 3^2, ,.....이 될 수 ..

연속합 문제 - https://www.acmicpc.net/problem/2579 문제요약 * 2156번 포도주 시식 문제랑 비슷하게 생각하면 된다. 그냥 숫자가 나열된 문제로 볼 수 있음. 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 각 계단에는 점수가 쓰여 있는데, 올라가면서 계단을 밟으면 계단에 쓰여있는 점수를 얻게 된다. 계단을 오르는 데는 다음과 같은 규칙이 있다. 1) 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있다. (즉, 한 계단을 밟으면 이어서 다음 계단이나 다다음 계단으로 오를 수 있다.) 2) 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 3) 마지막 도착 계단은 반드시 밟아야 한다. ex) s..

연속합 문제 - https://www.acmicpc.net/problem/1912 문제요약 n개의 정수로 이루어진 임의의 수열이 주어지면 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하라. ex) A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 연속된 수들의 합 중 가장 큰 값은 12 + 21 = 33 해결 방법 1. D[i] 정의 D[i] = "A[i]로 끝나는(까지 왔을 때의) 최대 연속합" 으로 정의할 수 있고, A[i]로 끝나는 최대 연속합은 두가지의 경우가 될 수 있다. 1) A[i-1]로 끝나는 최대 연속합에 A[i]가 포함되는 경우 => D[i-1] + A[i] 2) A[i]가 새로운 수열의 합으로 시작하는 경우 => A[i] 그러면 ..

가장 긴 바이토닉 부분 수열 문제 - https://www.acmicpc.net/problem/11054 문제요약 수열 A가 주어졌을 때, 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {1 5 2 1 4 3 4 5 2 1} 가장 긴 바이토닉 부분 수열 A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} => 길이는 7 해결 방법 * 최근에 푼 3개의 문제에 대한 이해가 있다면 이를 응용하여 풀 수 있다. - 바이토닉 수열의 꼭지값을 기준으로 왼쪽은 가장 긴 증가하는 부분 수열, 오른쪽은 가장 긴 감소하는 부분 수열을 찾아 이 둘의 길이를 합하여 구할 수 있다. 이를 조금만 다르게 생각해보면 "부분 수열의 마지막 원소로 A[i..

가장 긴 감소하는 부분 수열 문제 - https://www.acmicpc.net/problem/11722 문제요약 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열 A = {10, 30, 10, 20, 20, 10} => 길이는 3 해결 방법 * 바로 전전 문제를 조금 수정해서 풀 수 있다. 방법 1. 입력으로 주어진 수열을 reverse해서 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' 방법 2. 왼쪽 -> 오른쪽 순으로 값을 구하는 것이 아닌, 오른쪽 -> 왼쪽 순으로 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' (1) 구현..

가장 큰 증가 부분 수열 문제 - https://www.acmicpc.net/problem/11055 문제요약 수열 A가 주어졌을 때 증가 부분 수열 중에서 가장 수열의 합이 큰 것을 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 합이 가장 큰 증가 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} => 총 합은 1 + 2 + 50 + 60 = 113 해결 방법 * 바로 이전 문제를 조금 수정해서 풀 수 있다. 1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다. 다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다. 즉, D[N] 그 자체가 문제에서 원..

가장 긴 증가하는 부분 수열 문제 - https://www.acmicpc.net/problem/11053 문제요약 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {10, 20, 10, 30, 20, 50} 가장 긴 증가하는 부분 수열 A = {10, 20, 10, 30, 20, 50} => 길이는 4 해결 방법 1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다. 다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다. 즉, D[N] 그 자체가 문제에서 원하는 최종 결과값을 의미하지 않는다. 이런 맥락에서 D[i]를 아래와 같이 정의한 뒤 이들의 최대값을 통해 문제가 원하는 해답을 구할..

포도주 시식 문제 - https://www.acmicpc.net/problem/2156 문제요약 포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속적으로 놓여 있는 3잔을 모두 마실 수는 없다. 해결 방법1 (2차원 배열) 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "A[1]~A[N] 즉, N개의 포도주가 있을 때 가장 최대로 마실 수 있는 양" D[N][S] = "N개의 포도주 잔이 있고, N번째 포도주 잔의 상태가 S일 때 가장 최대로 마실 수 있는 양" S는 3가지 상태일 수 있..