[백준 1495번] 기타리스트 (java)

1495번: 기타리스트

문제의 예제로 각 연주마다 가능한 볼륨을 표현하면 다음과 같다.

연주가 반복될 때마다 위의 그래프처럼 가지가 증가하므로 뒤로 갈수록 계산해야 하는 양이 많아진다.

N의 범위가 최대 100이므로, N번째에는 2의 100승에 가까운 경우의 수를 검사해야 한다.

-> 메모리 초과 혹은 시간 초과

 

다른 방법을 생각하다가 M+1크기의 배열을 생성하고, 다음과 같이 의미를 부여했다.

int[] arr = new int[M+1];

arr[n] = m : m번째 연주에서 볼륨 n으로 연주를 할 수 있다.

 

위의 예제를 가지고 표현하면,

 

    - 0번째 연주에서 가능한 볼륨은 S = 5 이므로 arr[5] = 0로 설정한다.

    - 1번째 연주에서 가능한 볼륨은 0과 10이므로, arr[0] = 1, arr[10] = 1로 설정한다.

    - 2번째 연주에서 가능한 볼륨은 7과 3이므로 arr[7] = 2, arr[3] = 2로 설정한다.

    - 3번째 연주에서 가능한 볼륨은 10과 0이므로(14와 -4는 범위를 벗어나므로 안됨) 

      arr[10] = 3, arr[0] = 3로 설정한다.

 

즉, N번째 연주에서 가능한 볼륨을 찾으려면 원소값이 N이 되는 arr배열의 인덱스를 찾으면 될 것이다.

arr[?] = N

위를 만족하는 배열의 인덱스들 중에서 가장 큰 값이 N번째 연주에서 볼륨의 최대값이 된다.

 

단, 매번 임의의 볼륨 v이 0보다 크거나 같고, M보다 작거나 같은 지 확인한 후,

arr[v]에 값을 넣어주어야 한다. 볼륨이 범위를 벗어나는지 아닌지를 검사해줘야 한다.

 

전체 코드 :