Now or Never

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 ..

어느정도 풀다가 막혀서 이 해설을 보시는 분은, 풀이 힌트를 한번 보고 다시 혼자서 풀어보세요 1. 풀이 힌트 - 따로 노트에 2부터 12까지 세로로 숫자를 나열 한뒤, 각 숫자가 1이 되는 최소값을 비교해보라 그러면 규칙이 보일 것이다. 그래도 안보인다면 케이스를 16까지 늘려보라. 2. 풀이 과정 - 2부터 12까지 각 숫자를 1로 만드는 최소 연산횟수를 적어보면, 밑과 같이 나온다. 2(1), 3(1), 4(2), 5(3), 6(2), 7(3), 8(3), 9(2), 10(3), 11(4), 12(2) // 괄호 안은 각 숫자를 1로 만드는 연산의 최소횟수 1) 위의 결과를 기본으로 규칙을 찾기 위해 기본적으로 정수 N이 1씩 증가할 때 마다. 연산 횟수의 값도 1씩 증가한다고 가정한다. ex) 3..