import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int child[] = new int[n + 1];
int ans[] = new int[n + 1];
for (int i = 1; i <= n; i++) {
child[i] = in.nextInt();
}
ans[1] = 1;
for (int i = 2; i <= n; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (child[i] > child[j]) {
max = Math.max(max, ans[j]);
}
}
ans[i] = max + 1;
}
Arrays.sort(ans);
System.out.println(n - ans[n]);
}
}
오랜만에 코드 잼을 풀어볼까 해서 운동 갔다온 후 켰음. 역시 영어라서 문제푸는 시간보다 해석하는데 더 오래걸림ㅠ 영어공부 좀 해야겟다
코드잼 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();
}
}
모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어질 때, 2차원 배열 b의 경우의 수를 (10^7+ 19)로 나눈 나머지를 구하는 문제이다.
문제 조건
b의 모든 원소는 0 또는 1이며 a와 b의 크기가 같다
a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같다.
b의 각 행에 들어 있는 1의 개수가 짝수이다. (0도 짝수)
일단... 경우의 수를 ~~로 나눈 나머지를 구하라고 했으니 이 수가 엄청나게 클 것이고 그냥 구하면 시간 초과가 날 것이라는 것을 알 수 있다.
대개 이렇게 결과값의 나머지를 구하라는 문제는 dp로 푸는데, dp를 어떻게 적용하면 좋을지 생각해 봤다.
dp[i][j]: (0, 0) ~ (i, j)까지 조건에 맞는 b를 만들 수 있는 경우의 수라고 정의하자.
만약 행들 중 1의 개수가 짝수이면 1을 더하면 홀수가 될 것이고, 홀수이면 1을 더하면 짝수개가 될 것이다.
열 하나를 추가해서 새롭게 만들어지는 배열은 몇 개의 짝수행을 가지고 있을 것인가. 그리고 만들 수 있는 경우의 수는 어떻게 될까.
기존에 가지고 있던 짝수행의 개수는 num개 였고 k개의 행에 1을 추가한다고 했기 때문에 k개의 행이 홀수행이 될 것이고 남은num-k개가 여전히 짝수행일 것이다. 이 경우의 수는 기존 짝수행의 개수num개 중k개를 넣을 것이기 때문에 조합(num)C(k)이다.
기존에 가지고 있던 홀수행은 n-num개(전체 배열의 행 크기 - 짝수 행 크기) 일 것이다. 조건 2에 의해 입력배열에서 column+1 열의 1의 개수를 알 수 있고 이를 oneCnt라 하자. oneCnt 중 k개는 짝수행에 넣을 것이고 남은 oneCnt - k개의 1을 홀수행에 넣을 것이다. 따라서oneCnt-k개가 짝수행이 될 것이다. 이 경우의 수는 기존 홀수행의 개수n-num개 중oneCnt - k개를 넣을 것이기 때문에 조합(n-num)C(oneCnt-k)가 될 것이다.
위와 같이 짝수행, 홀수행의 경우를 독립사건으로 보고 각자의 경우의 수를 구했으면 두 경우의 수를 곱한 결과에dp[column][num]을 곱한 결과가 우리가 구하고자 하는 dp[column+1][(num-k) + (oneCnt-k)] 값이 된다.
문자열 형태의 숫자와, +, - 가 들어있는 배열의 계산 결과 중 최댓값을 구하는 문제이다
모든 경우에 대해 구하되, 구한 값을 어딘가 저장해 두어야 한다. => dp
dp[i][j]: 인덱스 i ~ j 까지 괄호 계산을 한 값이라고 정의하자.
이때, 양수 연산의 경우 뒤에 있는 값이 최대한 커야하고, 음수 연산의 경우 뒤에 있는 값이 최대한 작아야 최댓값을 구할 수 있다.
따라서 양수 연산이 앞에 있을 땐 dp에 최댓값을, 음수 연산이 앞에 있을 땐 dp에 최솟값을 저장하도록 한다.
class Solution {
public int solution(String arr[]) {
int n = arr.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MIN_VALUE;
}
if (i % 2 == 0) {
dp[i][i] = Integer.parseInt(arr[i]);
}
}
return calculateItoJ(arr, dp, 0, n - 1);
}
public static int calculateItoJ(String[] arr, int[][] dp, int i, int j) { // i부터 j까지 연산
if (dp[i][j] != Integer.MIN_VALUE) {
return dp[i][j];
}
if (i - 1 >= 1 && arr[i - 1].equals("-")) { // - 연산 처리: 뒷부분이 최소가 되어야
int result = Integer.MAX_VALUE;
for (int k = i; k < j; k += 2) {
int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
result = Math.min(result, subResult);
}
dp[i][j] = result;
} else { // + 연산 처리: 뒷부분이 최대가 되어야
int result = Integer.MIN_VALUE;
for (int k = i; k < j; k += 2) {
int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
result = Math.max(result, subResult);
}
dp[i][j] = result;
}
return dp[i][j];
}
public static int calculate(int a, String op, int b) {
if (op.equals("-")) {
return a - b;
}
if (op.equals("+")) {
return a + b;
}
return 0;
}
}
nums 배열에 있는 값을 적절히 더하고 빼서 target과 같은 값을 만들 수 있는 방법의 수를 구하는 문제이다.
일단 문제를 풀 수 있는 방법으로 가장 먼저 떠오른 것은 브루트 포스,,, 시간복잡도는 O(2^N)이다.
class Solution {
public int answer = 0;
public int findTargetSumWays(int[] nums, int S) {
findAll(nums, 0, 0, S);
return answer;
}
public void findAll(int[] nums, int index, int sum, int target) {
if (index >= nums.length) {
if (sum == target) {
answer++;
}
return;
}
findAll(nums, index + 1, sum - nums[index], target);
findAll(nums, index + 1, sum + nums[index], target);
}
}
이 방법 외에 다른 방법이 있지 않을까 생각해 봤다.
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.
문제 조건을 다시 보면 num의 합은 1000을 넘지 않는다고 했다.
합이 있으면 차도 가능하니 num을 적절히 더하고 빼면 그 범위는 -1000~1000일것이다.
이를 dp를 이용해서 구하도록 하는데, 음수 인덱스는 불가능 하니
dp[i][sum+1000]: num의 i번째 요소까지 더하고 뺐을 때, sum을 만들 수 있는 가짓수로 정의하도록 한다. 이 경우 시간복잡도는 O(N)이다.
import java.util.*;
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int[][] memo = new int[nums.length][2001];
for (int[] row : memo) {
Arrays.fill(row, Integer.MIN_VALUE);
}
return calculate(nums, 0, 0, S, memo);
}
public int calculate(int[] nums, int i, int sum, int S, int[][] memo) {
if (i == nums.length) {
if (sum == S) {
return 1;
}
return 0;
}
if (memo[i][sum + 1000] != Integer.MIN_VALUE) {
return memo[i][sum + 1000];
}
int add = calculate(nums, i + 1, sum + nums[i], S, memo);
int subtract = calculate(nums, i + 1, sum - nums[i], S, memo);
memo[i][sum + 1000] = add + subtract;
return memo[i][sum + 1000];
}
}
=> O(N^2), N ≤ 100000이므로 1초안에 통과될 수 없다. 아마 10초정도 걸릴것임...ㅠㅠ
dp[n]: n번째 수를 마지막으로 하는 최장증가부분수열로 정의했다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] stock = new int[n];
int[] dp = new int[n];
int max = 0;
for (int i = 0; i < n; i++) {
stock[i] = in.nextInt();
}
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (stock[i] > stock[j]) {
dp[i] = Math.max(dp[j], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}
}
2차 시도 - N ≤ 100000이므로 1초안에 통과하려면 시간복잡도가 적어도 NlogN을 되어야 한다. => `이분탐색`을 이용한다
stock 수열을 처음부터 보면서
1. dp의 끝 값과 비교했을 때 마지막 값보다 큰 경우 dp의 마지막에 바로 삽입
2. dp의 끝 값과 비교했을 때 마지막 값보다 작거나 같은 경우 이분탐색을 이용하여 LIS를 유지하기 위한 위치에 수를 삽입하도록 한다.
https://www.acmicpc.net/problem/3745 예제
stock[0]을 dp 리스트에 넣는다.
stock[1]이 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)
stock[2]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)
stock[3]은 1보다 크므로 바로 삽입
stock[4]는 4보다 크므로 바로 삽입
stock[5]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=1)
예제에서 볼 수 있듯이 최종 dp 수열은 진짜 최장 증가 부분 수열을 이루는 요소와는 상관 없으며, lis의 길이만 연관이 있다는 점이 중요하다
위 알고리즘을 적용하여 코드를 짜 보면 아래와 같다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] stock = new int[n];
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
stock[i] = in.nextInt();
}
dp[0] = stock[0];
int lastIndex = 0;
for (int i = 1; i < n; i++) {
if (dp[lastIndex] < stock[i]) {
lastIndex++;
dp[lastIndex] = stock[i];
} else {
int index = findIndex(dp, stock[i], lastIndex);
dp[index] = stock[i];
}
}
System.out.println(lastIndex + 1);
}
}
public static int findIndex(int[] dp, int num, int lastIndex) {
int left = 0;
int right = lastIndex;
while (left < right) {
int mid = (left + right) / 2;
if (dp[mid] == num) {
return mid;
}
if (dp[mid] > num) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
}
다른 방법으로는 `segment tree`를 사용하는 방법도 있다. segment tree를 사용하여 lis 길이를 구하는 방법은 아래와 같다.
1. 세그먼트 트리를 모두 0으로 초기화한다. , (stock[i], i) 객체를 만든 후 stock[i] 값에 대해 오름차순으로 정렬한다.
2. (stock[i], i)를 순회하면서 stock[i]에 대해구간 [0, i]에서 최댓값을 구하고, 그 최대값+1을 세그먼트 트리의 인덱스 i인 리프 노드 값으로업데이트한다. => i에 대해 구간 [0, i]에 지금까지 존재하는 LIS 길이+1 은 결국 stock[i]으로 끝나는 LIS길이와 같다.
3. 정렬된 객체를 순회하면서 LIS의 max 값을 찾는다.
가장 먼저 stock[i]=1인 i=2를 방문하게 된다.
먼저 구간 [0, 2]의 최댓값은 0이므로 1로 끝나는 LIS 길이는 1이고,
그 1 값을 인덱스 2에 업데이트 해 준다.
그 다음 stock[i]=2인 i=1를 방문하게 된다.
마찬가지로 [0, 1]의 최댓값은 0이므로 인덱스 1에 업데이트 해준다.
이때, 기존 LIS 결과가 증가하지는 않는다.
일단 이후 값이 언제 증가되는지 좀 더 보기로 하자.
그 다음 stock[i]=3인 i=5를 방문하게 되는데,
[0, 5]의 최댓값은 1이므로 인덱스 5에 2를 업데이트 해준다.
즉, 새로 보는 원소가 기존의 LIS 길이를 증가시키려면
그 원소가 기존의 LIS보다 뒤에 나타나야 한다.
=> 이를 확인하는 것이 결국 구간 [0, i]의 최댓값을 보는 것이다.
이렇게 세그먼트 트리를 이용하여 stock[i]의 위치에 i번째 수를 마지막 원소로 가지는 lis의 길이를 업데이트함으로써 lis의 가장 긴 길이를 구할 수 있다.
