[백준] 27114 조교의 맹연습 [자바]

 

 

---

https://st-lab.tistory.com/141

[백준] 12865번 : 평범한 배낭 - JAVA [자바]

https://upload.acmicpc.net/30f339f9-285f-43ef-bdf1-6da563423866/

 

※. 작업을 끝마쳤을 때 처음 바라보던 방향을 봐야한다.(360 회전)

 

※. 한 바퀴 회전하는 동작들은 총 6가지

(좌로 돌아 + 우로 돌아)

(좌로 돌아 + 좌로 돌아 + 뒤로 돌아)

(우로 돌아 + 우로 돌아 + 뒤로 돌아)

(뒤로 돌아 + 뒤로 돌아)

(좌로 돌아 + 좌로 돌아 + 좌로 돌아 + 좌로 돌아)

(우로 돌아 + 우로 돌아 + 우로 돌아 + 우로 돌아)

 

※. 한 바퀴 회전하는 모든 동작들은 6가지로 나눌 수 있다.

(우좌좌뒤좌 의 경우 -> 좌우 + 좌좌뒤, 좌우좌뒤뒤 의 경우 -> 좌우 + 좌뒤뒤)

 

※. 에너지를 기준으로 잡는 knapsack DP로 해결 가능하다.

(동일한 에너지를 사용하는 작업이 여럿 있으면 더 적은 작업수를 선택한다.)

 

---

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		long ans = 1_000_000;
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] turn = {A+A+A+A, B+B+B+B, C+C, C+B+B, C+A+A, A+B};
		int[] turn_cnt = {4,4,2,3,3,2};
		int[] cnt = new int[1_000_001];
		Arrays.fill(cnt, Integer.MAX_VALUE);
		for(int i = 0; i < 6; i++) {
			if(turn[i] <= K) {
				cnt[turn[i]] = Math.min(cnt[turn[i]], turn_cnt[i]);
			}
		}
		for(int i = 1; i <= 1_000_000; i++) {
			for(int j = 0; j < 6; j++) {
				if(i-turn[j] >= 0 && cnt[i-turn[j]] != Integer.MAX_VALUE) {
					cnt[i] = Math.min(cnt[i], cnt[i-turn[j]] + turn_cnt[j]);
				}
			}
		}
		if(cnt[K] == Integer.MAX_VALUE) cnt[K] = -1;
		System.out.println(cnt[K]);
	}
}