Now or Never

1. 풀이 힌트 - 백준 11053 - 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 부분 수열을 고려 할 때, 증가하는 값과 이어지는 감소하는 값을 고려한 바이토닉 수열의 길이를 구해야 한다. 따라서 증가에서 감소로 가는 부분에서, 증가할 때 이어지던 수열의 길이를 감소할 때 이어서 카운트 해주어야 한다 2. 풀이 과정 - 기본적으로 이전에 작성한 '가장 긴 증가하는 부분 수열의 풀이'를 기준으로 설명하겠다. 1) 밑의 표와 같이 증가하는 부분 수열의 크기만을 기록한 기존의 dp 배열을 2차원으로 확장하여 저장된 값, 증가하는 부분의 수열의 크기, 감소하는 수열의 크기(+ 바이토닉 구간)을 저장하는 새로운 배열을 선언해야 한다 표1) 증가하는 부분수열만 고려한 배열선언 arr (저장된 값) 10 20..

1. 풀이 힌트 - 어떤 인덱스의 크기를 기준으로 첫 번째 인덱스 부터 해당 인덱스 앞까지 값을 비교하면서, 부분 수열의 크기를 카운트해준다. 2. 풀이 과정 1) 6개의 숫자 10, 20, 10, 30, 20, 50를 저장하는 배열(arr)을 선언하고, 해당 배열안의 숫자들의 크기를 비교하여 부분 수열의 크기를 카운트한 수를 저장하는 배열(dp)을 선언한다. arr (저장된 값) 10 20 10 30 20 50 dp (큰 순서) 0 0 0 0 0 0 수열의 크기가 6이므로 총 6번의 비교 작업을 수행한다. 2) 첫번째 비교 작업 (i = 1)일 때는 첫번째 수가 가장 큰 수이므로 해당 dp값으로 +1을 추가한다. arr (저장된 값) 10 20 10 30 20 50 dp (큰 순서) 1 0 0 0 0 ..

1. 풀이 힌트 - 현재 인덱스에서 어떻게 와인을 먹어야 최대 값이 나올 수 있는지 케이스를 나눈 후 각 케이스중에 최대 값을 구한다 2. 풀이 과정 - 잔이 1개라면 현재 마실 수 있는 최대 양이다. - 잔이 2개라면 현재 마실 수 있는 최대 양은 두 잔을 더한 값이다. - 잔이 3개 이상이라면 연속해서 3잔 이상을 마실 수 없으므로 조건을 고려하여 현재 인덱스에서 마실 수 있는 최대의 양을 계산해야 한다. 최대 값이 나올 수 있는 케이스는 3가지가 있다 1) dp[i] = dp[i - 1] - dp[i]를 현재 인덱스(i)에서 마실 수 있는 최대 와인의 양이라고 했을 때, dp[i]는 dp[i - 1]가 되는 케이스이다. 예를 들어 각각 용량이 40, 50, 1인 와인잔이 있을 때 왼쪽부터 순서대로 ..

1. 풀이 힌트 - N의 자릿수 길이의 숫자에서 계단 수 조건으로 0부터 9까지의 숫자가 끝에 올 수 있는 횟수를 카운트한다. 앞의 규칙으로 4자리수 까지 구한뒤 비교해보면 규칙이 보일 것이다. ex) 한 자리수에서 0부터 9까지 숫자가 끝에 올 수 있는 경우의 수 N = 1 일 때 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 2. 풀이 과정 - 한 자리수 부터 네자리 까지 0 ~ 9의 숫자가 끝에 올수 있는 경우의 수를 나열하면 밑과 같다 0 1 2 3 4 5 6 7 8 9 // 0 ~ 9까지 0 1 1 1 1 1 1 1 1 1 // N = 1 1 2 2 2 2 2 2 2 2 1 // N = 2 2 3 4 4 4 4 4 4 3 2 // N = 3 3 6 7 7 7 7 7 7 ..