[DP] 백준 알고리즘 1514번 자물쇠

문제 : https://www.acmicpc.net/problem/1514

1. 시간초과는 아니지만 틀렸다고....

2. 좀더 확인이 필요. 방법이 잘못되었는지.

소스코드

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Baekjoon1514 {
//public class Main {
	
	public static void main(String[] args) 
			throws FileNotFoundException 
	{

		File file =new File("D:\\dev\\worksspace\\Solution\\src\\Baekjoon1514");
		Scanner sc = new Scanner(file);
//		Scanner sc = new Scanner(System.in);
		
//		long start = System.currentTimeMillis();
		
		while (sc.hasNext()) {
			
			int numCnt = sc.nextInt();
			String curSt = sc.next(); 
			String goalSt = sc.next(); 
			
			int[] curArr = new int[numCnt+2];
			int[] goalArr = new int[numCnt+2];
			
			for (int i = 0; i < numCnt; i++) {
				curArr[i] = Integer.parseInt(curSt.substring(i,i+1));
				goalArr[i] = Integer.parseInt(goalSt.substring(i,i+1));
			}
			
			int answer = 0; // 움직인 cnt
			
			int[][][] jArr = new int[20][20][20]; // 목표값과 일정 차이일때, 최적 j
			int[][][] kArr = new int[20][20][20]; // 목표값과 일정 차이일때, 최적 k
			
			//알고리즘 시작
			for (int i = 0; i < numCnt; i++) {
				while (curArr[i] != goalArr[i]) {
					
					int maxK = Math.min(numCnt-i,3);
					int targetJ = 99;
					int targetK = 0;
					
					if(maxK == 3 && jArr[curArr[i]-goalArr[i]+10][curArr[i+1]-goalArr[i+1]+10][curArr[i+2]-goalArr[i+2]+10] != 0){
						targetJ = jArr[curArr[i]-goalArr[i]+10][curArr[i+1]-goalArr[i+1]+10][curArr[i+2]-goalArr[i+2]+10];
						targetK = kArr[curArr[i]-goalArr[i]+10][curArr[i+1]-goalArr[i+1]+10][curArr[i+2]-goalArr[i+2]+10];
					}else{
						
						//1. 위아래 몇번 움직일지 정하기.
						int jDiff = 99;
						for (int j = -3; j <= 3; j++) { // 위아래 -3~3
							int tempdiff = Math.abs(curArr[i]+j - goalArr[i]);
							if(tempdiff <jDiff){
								jDiff = tempdiff;
								targetJ = j;
							}
						}
						
						
						//2. 첫번째 값의 차이가 가장 적을때,
						int minDiff = 999;
						
						for (int k = 1; k <= maxK; k++) { // 갯수 : 1개 2개 3개
							
							int tempDiff = 0;
							int tempVal = 0;
							for (int j = 0; j < 3; j++) {
								if(j < k){
									tempVal = (curArr[i+j]+targetJ+10)%10 - goalArr[i+j];
								}else{
									tempVal = curArr[i+j] - goalArr[i+j];
								}
								tempVal = Math.abs(tempVal);
								tempVal = tempVal > 5 ? 10-tempVal : tempVal;
								tempDiff += tempVal;
							}
							if(tempDiff <= minDiff){ 
								//여기서 애매함. <로 쓸지 <=일지 다른기준이필요한지
								targetK = k;
								minDiff = tempDiff;
							}
						}
						
						//3. dp 값 insert
						if(maxK == 3){
							jArr[curArr[i]-goalArr[i]+10][curArr[i+1]-goalArr[i+1]+10][curArr[i+2]-goalArr[i+2]+10] = targetJ;
							kArr[curArr[i]-goalArr[i]+10][curArr[i+1]-goalArr[i+1]+10][curArr[i+2]-goalArr[i+2]+10] = targetK;
						}
					}
					
					
					//4. curArr Update;
					for (int j = 0; j < targetK; j++) {
						curArr[i+j] = (curArr[i+j]+targetJ+10)%10;
					}
					
					answer++;
					
					//5.로그.....
					for (int j = 0; j < numCnt; j++) {
						System.out.print(curArr[j]);
					}
					System.out.println();
					System.out.println("j:" + targetJ+", k:"+targetK);
					System.out.println();
				}
				
			}
			System.out.println(answer);
			
		}
		
//		long end = System.currentTimeMillis();
//		System.out.println("time "+ (end-start)/1000.0);
	}
}

/*
3
555 
464

2

4
1234
3456

2

*/