글 읽기 - 반례 부탁드려도 될까요? (+DP로 되는게 맞을까요?)

nahwasa 4년 전 0

우선은 완전탐색이면 풀순있겠으나, 당연히 시간초과날것같이 생겨서 시도를 안해봤습니다.

그리고 문제 생긴게 DP문제같아서 DP로 진행해봤는데 혹시 반례 부탁드려도 될까해서 여쭤봅니다.

20000 짜리가 최대 100개이니 오버플로우 문제도 아닌듯하구요.

진행한 방식은 3차원 배열로 DP를 진행했습니다.

예를들어 기본 TC의 첫번째의 경우

입력
5 900
800 700 400 300 200

테스팅
0|0       0|0       800|0    
1400|1    700|0     700|0    
1800|2    1200|0    400|0    
2066|3    1700|1    1100|0    
2243|4    2000|2    1600|0

위의 입력에 대해 테스팅 부분처럼 한 로우씩 각 N번째 시간을 뜻합니다. (dp[A][B][C]에서 A를 의미)

첫번째 컬럼은 그냥 먹을 시, 두번째는 한칸 건너띄고 먹을 시, 세번째는 두칸 건너띄고 먹을 시 입니다. (dp[A][B][C]에서 B를 의미)

'|' 로 나뉜 문자는 좌측은 현재까지의 합, 우측은 2/3씩 나누어 내려갈 때 현재 몇번째인지를 나타냅니다. (dp[A][B][C]에서 C를 의미)

(그냥 먹으면 +1, 한칸 건너띄면 그대로, 두칸 건너띄면 초기화)

입력
5 900
800 700 40 300 200

테스팅
0|0       0|0       800|0    
1400|1    700|0     700|0    
1440|2    840|0     40|0    
1706|3    1700|1    1100|0    
1900|2    1640|2    1600|0

같은 방식으로 기본 TC의 두번째는 아래와 같습니다. (주석처리된 //for test 아래부분이 테스팅 문자열 출력)

궁금한점은

우선 이런방식으로 풀 수 있는 문제가 맞나요? 한가지 걸리는 점은, 현재는 어떠한 위치에서 -1, -2, -3 위치만 보면서 계산하는데 이 방식만으로 최적해를 구할 수 있다는 보장이 없으면 애초에 이걸로 못푸는데, 그 증명을 못하겠습니닼ㅋㅋㅋ 그냥 dp로 될꺼같은데?! 해서 해보고 있던중입니다.
혹시 반례 있으면 부탁드립니다 ㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int M = 0;
	static int[] arr = null;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		// input & init
		int N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		int[][][] dp = new int[N][3][2];
		// set dp base
		dp[0][2][0] = Math.min(arr[0], getM(0));
		dp[0][2][1] = 0;
		// dp
		for (int i = 1; i < N; i++) {
			for (int k = 0; k < 3; k++) {
				switch(k) {
				case 0 :	// 그냥 먹음 (-1에서 최대값의 2/3)
					dp[i][k] = max(dp[i-1], i, k);
					break;
				case 1 : 	// 한번 건너띄고 먹음 (-2에서 최대값과 동일)
					dp[i][k] = max(i==1?null:dp[i-2], i, k);					
					break;
				case 2 : 	// 두번 건너띄고 먹음 (M까지)			
					dp[i][k] = max((i==1||i==2)?null:dp[i-3], i, k);
					break;
				}
			}
		}
		int result = 0;
		for (int i = 0; i < 3; i++)
			result = Math.max(result, dp[N-1][i][0]);
		bw.write(result + "\n");
		//for test
//		for (int i = 0; i < N; i++) {
//			for (int k = 0; k < 3; k++) {
//				bw.write(dp[i][k][0] + "|" + dp[i][k][1] + "\t");
//			}
//			bw.newLine();
//		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static int[] max(int[][] tg, int cur, int dpIdx) {
		int[] result = new int[2];
		int calc = 0;
		// exception
		if ((dpIdx == 1 && cur-2 < 0) || (dpIdx == 2 && cur-3 < 0)) {	// 건너띈 경우가 없음. idx 0번에서 안먹은경우.
			result[0] = Math.min(M, arr[cur]);
			return result;
		}		
		for (int i = 0; i < 3; i++) {
			switch(dpIdx) {
			case 0 :
				calc = tg[i][0] + Math.min(getM(tg[i][1]+1), arr[cur]);
				if (calc > result[0]) {
					result[0] = calc;
					result[1] = tg[i][1]+1;
				}
				break;
			case 1 :				
				calc = tg[i][0] + Math.min(getM(tg[i][1]), arr[cur]);
				if (calc > result[0]) {
					result[0] = calc;
					result[1] = tg[i][1];
				}
				break;
			case 2 :
				calc = tg[i][0] + Math.min(M, arr[cur]);
				if (calc > result[0]) {
					result[0] = calc;
					result[1] = 0;
				}
				break;
			}			
		}			
		return result;
	}
	
	private static int getM(int idx) {
		int result = M;
		for (int i = 0; i < idx; i++) {
			result =result*2/3;
		}
		return result;
	}
}

nahwasa 4년 전 0

생각해보니 2/3로 나뉘는 부분때문에, 오히려 현재로써는 최대치가 아니더라도 숫자 낮은쪽을 고르는게 이득일 경우가 생기겠네요.

그럼 4차원 배열로 2/3로 몇번 나눴는지를 따로 관리해야하려나 싶네요 -_-;;

뭔가 애초에 이렇게 어려운 문제가 아니지 않을가도 싶고.. 실력이 부족해서 확신을 못하겠군요;

sait2000 4년 전 1

반례 드립니다.

in:
900
600 400 266 177 118 78 52 34 22 14 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 15

out:
2816

note:
o	900
o	600
o	400
o	266
o	177
o	118
o	78
o	52
o	34
o	22
x	0
x	0
o	900
o	600
o	400
o	266
o	177
o	118
o	78
o	52
o	34
x	0
o	34
x	0
o	34
x	0
o	34
x	0
o	34
x	0
o	34
x	0
o	34