고양멍멍이

[문제링크]

0. 구현문제.. 구현한다...

1. 왼쪽으로 회전 = 오른쪽으로 회전 3번과 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[]color=new char[] {'w','g','r','b','o','y'};
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			//주사위 만들기
			cube=new char[6][3][3];
			
			for (int i = 0; i < 6; i++) {
				for (int j = 0; j < 3; j++) {
					Arrays.fill(cube[i][j], color[i]);
					
				}
			}
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int i = 0; i < N; i++) {
				String oper = st.nextToken();
				//1:시계, 0:반시계
				int dir = oper.charAt(1)=='+'?1:0;
				
				switch (oper.charAt(0)) {
				case 'U':
					rotate_0();
					if(dir==0) {
						rotate_0();
						rotate_0();
					}
					break;
				case 'L':
					rotate_1();
					if(dir==0) {
						rotate_1();
						rotate_1();
					}
					break;
				case 'F':
					rotate_2();
					if(dir==0) {
						rotate_2();
						rotate_2();
					}
					break;
				case 'R':
					rotate_3();
					if(dir==0) {
						rotate_3();
						rotate_3();
					}
					break;
				case 'B':
					rotate_4();
					if(dir==0) {
						rotate_4();
						rotate_4();
					}
					break;
				case 'D':
					rotate_5();
					if(dir==0) {
						rotate_5();
						rotate_5();
					}
					break;
				default:
					break;
				}
				
				
			}//end of oper

			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					System.out.print(cube[0][i][j]);
				}
				System.out.println();
			}
		}//end of tc
		
	}
	static char[][][]cube;
	static int[][]pos = new int[][] {
		{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}
	}; 
	static void rotate(int n) {
		//자기 판 회전
		char[] backup=new char[] {cube[n][0][0],cube[n][0][1]};
		for (int i = 7; i >=0; i--) {
			cube[n][ pos[(i+2)%8][0] ][ pos[(i+2)%8][1] ] =
					cube[n][ pos[i][0] ][ pos[i][1] ];
		}
		cube[n][0][2]=backup[0];
		cube[n][1][2]=backup[1];
	}
	
	static void rotate_0() {
		//1234 다 위쪽
		rotate(0);
		char[]backup=cube[1][0].clone();
		//4개의 주변 판 회전
		cube[1][0]=cube[2][0].clone();
		cube[2][0]=cube[3][0].clone();
		cube[3][0]=cube[4][0].clone();
		cube[4][0]=backup.clone();
	}
	
	static void rotate_1() {
		//0왼 2왼 5왼 4오
		rotate(1);
		char[]backup=new char[] {cube[0][0][0],cube[0][1][0],cube[0][2][0]};
		//2->5->4->0
		cube[0][0][0]=cube[4][2][2];
		cube[0][1][0]=cube[4][1][2];
		cube[0][2][0]=cube[4][0][2];
		
		cube[4][2][2]=cube[5][0][0];
		cube[4][1][2]=cube[5][1][0];
		cube[4][0][2]=cube[5][2][0];
		
		cube[5][0][0]=cube[2][0][0];
		cube[5][1][0]=cube[2][1][0];
		cube[5][2][0]=cube[2][2][0];
		
		cube[2][0][0]=backup[0];
		cube[2][1][0]=backup[1];
		cube[2][2][0]=backup[2];

	}
	static void rotate_2() {
		//0아 3왼 5위 1오
		rotate(2);
		char[]backup=new char[] {cube[0][2][0],cube[0][2][1],cube[0][2][2]};
		//3-5-1-0
		cube[0][2][0]=cube[1][2][2];
		cube[0][2][1]=cube[1][1][2];
		cube[0][2][2]=cube[1][0][2];
		
		cube[1][0][2]=cube[5][0][0];
		cube[1][1][2]=cube[5][0][1];
		cube[1][2][2]=cube[5][0][2];
		
		cube[5][0][0]=cube[3][2][0];
		cube[5][0][1]=cube[3][1][0];
		cube[5][0][2]=cube[3][0][0];
		
		cube[3][2][0]=backup[2];
		cube[3][1][0]=backup[1];
		cube[3][0][0]=backup[0];
	}
	static void rotate_3() {
		//0오 5왼 6오 3오
		rotate(3);
		char[]backup=new char[] {cube[0][0][2],cube[0][1][2],cube[0][2][2]};
		//4-5-2-0
		cube[0][0][2]=cube[2][0][2];
		cube[0][1][2]=cube[2][1][2];
		cube[0][2][2]=cube[2][2][2];

		cube[2][0][2]=cube[5][0][2];
		cube[2][1][2]=cube[5][1][2];
		cube[2][2][2]=cube[5][2][2];

		cube[5][0][2]=cube[4][2][0];
		cube[5][1][2]=cube[4][1][0];
		cube[5][2][2]=cube[4][0][0];
		
		cube[4][2][0]=backup[0];
		cube[4][1][0]=backup[1];
		cube[4][0][0]=backup[2];
	}
	static void rotate_4() {
		//1위 2왼 6아 4오
		rotate(4);
		char[]backup=new char[] {cube[0][0][0],cube[0][0][1],cube[0][0][2]};
		//1-5-3-0
		cube[0][0][0]=cube[3][0][2];
		cube[0][0][1]=cube[3][1][2];
		cube[0][0][2]=cube[3][2][2];
		
		cube[3][0][2]=cube[5][2][2];
		cube[3][1][2]=cube[5][2][1];
		cube[3][2][2]=cube[5][2][0];
		
		cube[5][2][2]=cube[1][2][0];
		cube[5][2][1]=cube[1][1][0];
		cube[5][2][0]=cube[1][0][0];
		
		cube[1][2][0]=backup[0];
		cube[1][1][0]=backup[1];
		cube[1][0][0]=backup[2];
	}
	static void rotate_5() {
		//4321 다 아래쪽
		rotate(5);
		char[]backup=cube[1][2].clone();
		//2-3-4-1
		cube[1][2]=cube[4][2].clone();
		cube[4][2]=cube[3][2].clone();
		cube[3][2]=cube[2][2].clone();
		cube[2][2]=backup.clone();
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 그리디를 이용해 가격 구하기

  - n번 동전의 가치가 w이고, n-1번 동전까지 사용하여 w-1 금액까지는 옳은 해가 구해져 있다면

  - w원 이후의 가격 x에 대해선 ( (x%w)의 최적해 + (x/w) ) 이 최적해이다

  - ex) 한국 동전에 대해, w가 500원일때 650원의 최적해는 (150원의 최적해 + 1) 이다

  - DP는 이 문제에서 항상 옳은 해를 구할 수 있다

  - DP를 이용해 구한 해와 그리디를 이용해 구한 해가 일치한다면, 그리디가 최적해를 구하는 것

  - 그리디를 통해 w ~ 2*w까지 최적해를 구할수 있다고 하면, 2*w ~ 이후에 대해서도 최적해가 보장된다

  - n+1번째 동전의 가치가 2*w보다 작다면 n+1번 동전까지만 최적해를 증명해도 된다

  - 즉, n번째 동전에 대해, min( 2*w(n) , w(n+1) ) 까지 최적해 여부를 검증

1. 정답은 기본값 Yes로 두고, 모든 동전에 대해 최적해 일치 여부를 검사한다

2. 현재 금액 i가 n번 코인의 화폐가치 w보다 작을 경우, w까지 진행한다

3. w부터 min( w*2, w[n+1] ) 금액까지 그리디 방식으로 해를 만든다

4. w부터 min( w*2, w[n+1] ) 금액까지 DP방식으로 해를 만들며, 그리디의 해와 비교한다

  - 중간에 불일치하는 값이 존재하면, 답을 No로 바꾸고, break한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int[] coin = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			coin[i]=pint(st.nextToken());
		}
		int[] valid = new int[coin[N-1]*2+1];//최대 20만 1
		valid[1]=1;//1원은 항상 1.
		
		String answer = "Yes";
		
		int coinIdx=1;
		for (int i = 1; i < coin[N-1]*2+1 && coinIdx<N; i++) {

			i = Math.min(2*i-1, coin[coinIdx]-1);
			//coin[i]번의 화폐가치까지 정상진행
			while(i<coin[coinIdx]) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k < coinIdx; k++) {
					if(1 + valid[i-coin[k]] < realcosti)realcosti=1 + valid[i-coin[k]];
				}valid[i++]=realcosti;
			}
			
			//valid[i] ~ 2 i까지 그리디로, +1해서 제작
			int destination = i*2;
			if(coinIdx<N-1)destination = Math.min(i*2, coin[coinIdx+1]);
			for (int j = i; j <= destination; j++) {
				valid[j]=valid[j-i]+1;
			}
			
			//직접 계산해가면서 valid[j]와 계산값이 같은지 비교. 다르면 바로 탈출
			//i-1번까지의 동전만 사용해서 i ~ 2*i의 값들을 계산해보기
			for (int j = i; j <= destination; j++) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k <= coinIdx; k++) {
					if(1 + valid[j-coin[k]] < realcosti)realcosti=1 + valid[j-coin[k]];
				}
				if(realcosti != valid[j]) {
					answer = "No";
					i=coin[N-1]*2+1;//for문 종료 목적
					break;
				}
			}
			coinIdx++;
		}
		System.out.println(answer);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}