문제 링크
문제
티어: 골드 1
알고리즘: dp
입력
입력은 세 줄로 이루어진다.
첫 번째 줄에 초기에 왼손 검지와 오른손 검지가 위치한 건반 위의 음이 차례대로 공백으로 구분되어 주어진다. 이때 두 음의 음정은 1 이상이다.
두 번째 줄에는 양의 정수 N이 주어진다.
세 번째 줄에는 악보가 주어지는데, N개의 음들이 순서대로 공백으로 구분되어 주어진다.
출력
첫째 줄에 악보를 완주하기 위해 두 손가락이 이동한 총 거리를 출력한다. 둘째 줄에 N개의 음을 연주한 방법을 공백으로 구분하여 출력한다. i(1 ≤ i ≤ N)번 째 음을 왼손 검지로 누른 경우 1을, 오른손 검지로 누른 경우 2를 출력한다.
제한
음은 Xy 또는 Xy# 형식의 2이상 3이하의 문자열로 주어진다. 여기서 X는 'A'부터 'G' 사이의 알파벳 대문자 중 하나이고, y는 음이 아닌 정수이다. (0 ≤ y ≤ 9)
풀이
민정이가 악보를 완주하기 위해 두 손가락이 이동해야 하는 거리의 최솟값을 구해야 한다.
왼손과 오른손의 위치가 정해졌을 때 다음 경우의 수는
- 왼손으로 악보의 첫 번째 음표를 치는 경우
- 오른손으로 악보의 첫 번째 음표를 치는 경우
이렇게 두 가지 존재한다.
그리고 다음부터는 왼손과 오른손의 위치가 다양할 것인데, 만약 왼손, 오른손의 위치가 같고, 다음번에 쳐야 될 악보의 위치가 같은 경우 가장 적은 횟수만이 최선이 된다.
이후부터는 완전히 같은 경우의 수를 가지고 있기 때문이다.
이를 토대로 dp를 정의하면 dp[left][right][N]이 되고,
예를 들어dp[3][5][3]이라면, 왼손이 3에 위치하고, 오른손이 5에 위치하고, 3번 째 음표까지 친 경우 최적 값을 의미한다.
이 문제는 아이디어보다는 구현이 훨씬 어려운 문제다. 나는 C0부터 1값을 부여해서 모든 음표를 int 값으로 변환해줬다.
그리고 주의할 점은 F0와 E0#, C1과 B0#의 음정 거리가 0이기 때문에 이를 어떻게 처리할지가 중요하다.
나는 단순히 1에서 10을 쳤을 때 빼줘야 할 값을 미리 구해놨다. 그래서 (10 - 1)에서 ebCnt[1][10]를 빼줌으로써 거리를 정확한 거리를 측정해줬다.
이 풀이의 시간 복잡도는 O(140 x 140 x 1000)이다.
소스 코드
import java.io.*;
import java.util.*;
class State {
int f, v;
State before;
State(int f, int v, State before) {
this.f = f;
this.v = v;
this.before = before;
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(br.readLine());
State[][][] dp = new State[141][141][N + 1];
dp[findIndex(st.nextToken())][findIndex(st.nextToken())][0] = new State(0, 0, null); //f는 1, 2;
int[][] ebCnt = new int[141][141];
for(int i=1; i<=140; i++) {
int before = 0;
for(int j=i + 1; j<=140; j++) {
if(find(j) == 7 || find(j) == 1) {
before += 1;
}
ebCnt[i][j] = before;
}
}
for(int i=140; i>=1; i--) {
int before = 0;
for(int j=i - 1; j>=1; j--) {
if(find(j) == 0 || find(j) == 6) {
before += 1;
}
ebCnt[i][j] = before;
}
}
int[] sheetMusic = new int[N + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
sheetMusic[i] = findIndex(st2.nextToken());
}
for(int i=1; i<=N; i++) {
for(int l=1; l<=140; l++) {
for(int r=1; r<=140; r++) {
if(dp[l][r][i - 1] != null) {
//존재한다면
//왼손에서 -> sheetMusic[i]까지
int nextV = Math.abs(l - sheetMusic[i]) - ebCnt[l][sheetMusic[i]] + dp[l][r][i - 1].v;
if(dp[sheetMusic[i]][r][i] == null || (nextV < dp[sheetMusic[i]][r][i].v)) {
dp[sheetMusic[i]][r][i] = new State(1, nextV, dp[l][r][i - 1]);
}
//오른손에서 -> sheetMusic[i]까지
int nextVr = Math.abs(r - sheetMusic[i]) - ebCnt[r][sheetMusic[i]] + dp[l][r][i - 1].v;
if(dp[l][sheetMusic[i]][i] == null || (nextVr < dp[l][sheetMusic[i]][i].v)) {
dp[l][sheetMusic[i]][i] = new State(2, nextVr, dp[l][r][i - 1]);
}
}
}
}
}
State answer = new State(-1, Integer.MAX_VALUE, null);
for(int i=1; i<=140; i++) {
for(int j=1; j<=140; j++) {
if(dp[i][j][N] != null) {
if(dp[i][j][N].v < answer.v) {
answer = dp[i][j][N];
}
}
}
}
StringBuilder sb = new StringBuilder();
sb.append(answer.v).append("\n");
Stack<Integer> stack = new Stack<>();
while(answer.before != null) {
stack.push(answer.f);
answer = answer.before;
}
while(!stack.isEmpty()) {
sb.append(stack.pop()).append(" ");
}
System.out.println(sb.toString().trim());
}
static int findIndex(String note) {
int result = 0;
if(note.charAt(0) == 'C') {
result += 1;
} else if(note.charAt(0) == 'D') {
result += 3;
} else if(note.charAt(0) == 'E') {
result += 5;
} else if(note.charAt(0) == 'F') {
result += 7;
} else if(note.charAt(0) == 'G') {
result += 9;
} else if(note.charAt(0) == 'A') {
result += 11;
} else if(note.charAt(0) == 'B') {
result += 13;
}
result += 14 * (note.charAt(1) - '0');
if(note.length() == 3) {
result += 1;
}
return result;
}
static int find(int nInd) {
int v = nInd % 14;
return v;
}
}