공부 기록

오랜만에 코드 잼을 풀어볼까 해서 운동 갔다온 후 켰음. 역시 영어라서 문제푸는 시간보다 해석하는데 더 오래걸림ㅠ 영어공부 좀 해야겟다

코드잼 Qualification 라운드는 30점만 넘기면 다음 라운드에 참가할 수 있다.

Reversort

주어진 reversort 슈도 코드를 시키는대로 구현하면 되는 문제였다

import java.util.*;

public class Solution {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			int n = in.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = in.nextInt();
			}

			int answer = 0;
			for (int i = 0; i < arr.length - 1; i++) {
				int j = minIndex(i, arr);
				reverse(i, j, arr);

				answer += (j - i + 1);
			}

			System.out.println("Case #" + t + ": " + answer);
		}
	}

	private static void reverse(int start, int end, int[] arr) {
		for (int i = 0; i <= (end - start) / 2; i++) {
			int temp = arr[start + i];
			arr[start + i] = arr[end - i];
			arr[end - i] = temp;
		}
	}

	private static int minIndex(int start, int[] arr) {
		int index = start;
		int value = arr[start];
		for (int i = start; i < arr.length; i++) {
			if (value > arr[i]) {
				value = arr[i];
				index = i;
			}
		}
		return index;
	}
}

Moons and Umbrellas

CJ가 나타나면 값x, JC가 나타나면 값y를 지불할 때 가장 작은 값을 리턴하는 문제이다.

일단은.. 테스트셋 2까지만 맞추는 것을 목표로 문제를 풀었다.

변수 범위는 아래와 같다.

1≤S.length()≤1000
1≤X≤100
1≤Y≤100

?가 있을 수 있는 값은 1000가지이고 모든 경우에 대해 구할 때 2^1000이 나와버리기 때문에 DP를 사용해야겠다고 생각했다.

dp[i][0]: 인덱스 i 가 ?일때, C를 넣을때 최솟값

dp[i][1]: 인덱스 i 가 ?일때, J를 넣을 때 최솟값으로 두고 아래와 같은 방식으로 풀어보기로 했다.

if-else, case문이 넘 드러워서 좀 간단히 할 수 있을 것 같긴 하지만... 일단 제출한 풀이는 아래와 같다.

import java.util.*;

public class Solution {

	private static final int C = 0;
	private static final int J = 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			int x = in.nextInt(); // CJ
			int y = in.nextInt(); // JC
			char[] input = in.next().toCharArray();
			int length = input.length;

			int dp[][] = new int[length][2];
			for (int i = 1; i < length; i++) {
				if (input[i] == '?') {
					switch (input[i - 1]) {
					case '?':
						dp[i][C] = Math.min(dp[i - 1][C], dp[i - 1][J] + y);
						dp[i][J] = Math.min(dp[i - 1][J], dp[i - 1][C] + x);
						break;
					case 'C':
						dp[i][C] = dp[i - 1][C];
						dp[i][J] = dp[i - 1][C] + x;
						break;
					case 'J':
						dp[i][C] = dp[i - 1][J] + y;
						dp[i][J] = dp[i - 1][C];
						break;
					}
				} else if (input[i] == 'C') {
					switch (input[i - 1]) {
					case '?':
						dp[i][C] = Math.min(dp[i - 1][C], dp[i - 1][J] + y);
						dp[i][J] = Math.min(dp[i - 1][C], dp[i - 1][J] + y);
						break;
					case 'C':
						dp[i][C] = dp[i - 1][C];
						dp[i][J] = dp[i - 1][J];
						break;
					case 'J':
						dp[i][C] = dp[i - 1][C] + y;
						dp[i][J] = dp[i - 1][J] + y;
						break;
					}
				} else { // input[i] == 'J'
					switch (input[i - 1]) {
					case '?':
						dp[i][C] = Math.min(dp[i - 1][C] + x, dp[i - 1][J]);
						dp[i][J] = Math.min(dp[i - 1][C] + x, dp[i - 1][J]);
						break;
					case 'C':
						dp[i][C] = dp[i - 1][C] + x;
						dp[i][J] = dp[i - 1][J] + x;
						break;
					case 'J':
						dp[i][C] = dp[i - 1][C];
						dp[i][J] = dp[i - 1][J];
						break;
					}
				}
			}
			System.out.println("Case #" + t + ": " + Math.min(dp[length - 1][0], dp[length - 1][1]));
		}
	}
}

Reversort Engineering

요번에는 1번 Reversort와 달리 cost가 주어지면 리스트를 찾는 문제이다. 불가능하면 IMPOSSIBLE을 리턴하도록 한다.

일단 테스트셋 1의 경우 2≤N≤7이므로 permutation을 모두 구한 뒤 cost를 계산하고, 알맞은지 알아보도록 했다.

(이렇게 풀면 당연히 테스트셋2는 2≤N≤100이기 때문에 TLE가 나온다... 어떻게 해야하는지 모르겟음.. cost를 적당히 합으로 나눠서 리스트를 만드는건가.. 나중에 다른 사람들 풀이 봐야겟다..)

import java.util.*;

public class Solution {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			int n = in.nextInt();
			int cost = in.nextInt();

			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = i + 1;
			}

			boolean isPossible = calculateCost(arr) == cost;

			// create permutations
			while (!isPossible) {
				int idex = findIndex(arr, n);
				if (idex == -1) {
					break;
				}

				int jdex = 0;
				for (int j = n - 1; j >= idex; j--) {
					if (arr[j] > arr[idex - 1]) {
						jdex = j;
						break;
					}
				}

				int temp = arr[jdex];
				arr[jdex] = arr[idex - 1];
				arr[idex - 1] = temp;

				int brr[] = new int[n];
				int bindex = 0;
				for (int i = 0; i < idex; i++) {
					brr[bindex++] = arr[i];
				}
				for (int i = n - 1; i >= idex; i--) {
					brr[bindex++] = arr[i];
				}
				if (calculateCost(brr) == cost) {
					isPossible = true;
					arr = brr;
					break;
				}
				arr = brr;
			}
			System.out.print("Case #" + t + ": ");
			printAnswer(arr, isPossible);
		}
	}

	private static int findIndex(int arr[], int n) {
		for (int i = n - 1; i >= 1; i--) {
			if (arr[i - 1] < arr[i])
				return i;
		}
		return -1;
	}

	private static int[] clone(int[] list) {
		int[] newList = new int[list.length];
		for (int i = 0; i < list.length; i++) {
			newList[i] = list[i];
		}
		return newList;
	}

	private static int calculateCost(int[] arr) {
		int[] list = clone(arr);
		int answer = 0;
		for (int i = 0; i < list.length - 1; i++) {
			int j = minIndex(i, list);
			reverse(i, j, list);

			answer += (j - i + 1);
		}
		return answer;
	}

	private static void reverse(int start, int end, int[] arr) {
		for (int i = 0; i <= (end - start) / 2; i++) {
			int temp = arr[start + i];
			arr[start + i] = arr[end - i];
			arr[end - i] = temp;
		}
	}

	private static int minIndex(int start, int[] arr) {
		int index = start;
		int value = arr[start];
		for (int i = start; i < arr.length; i++) {
			if (value > arr[i]) {
				value = arr[i];
				index = i;
			}
		}
		return index;
	}

	private static void printAnswer(int[] answer, boolean isPossible) {
		if (!isPossible) {
			System.out.println("IMPOSSIBLE");
			return;
		}

		for (int a : answer) {
			System.out.print(a + " ");
		}
		System.out.println();
	}
}

여기까지.. 31점을 얻었다 일단은..