[SWEA] 1244. 최대 상금

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

SW Expert Academy

 

문제를 보면서 처음 한 생각.

완탐이 가능한가? => 최대 6C2(15)^10 => 안돼.

 

하고 어떻게 할까 고민해보니깐

그리디하게 풀면 될꺼 같아서 이렇게 접근했고 접근과정은 맞긴 했다.

 

조건 1.

1 ~ n 번째까지 가면서

1번째를 기준으로 잡고 그것의 오른쪽에 있는 수들중 제일 큰 수

2번째를 기준으로 잡고 그것의 오른쪽에 있는 수들중 제일 큰 수

......

이렇게 나갔다. 그리고 수가 좀 적은거 같으니깐 만약 제일 큰수가 여러개가 있다면 

 

ex) 3 2 7 7 7 이 있으면

 

3 을 기준으로 잡고 max_num을 구하면 7인데 7이 3개가 있으니깐 

7 2 3 7 7 (1번째와 3번쨰 swap)

7 2 7 3 7 (1번째와 4번째 swap)

7 2 7 7 3 (1번째와 5번째 swap)

 

이렇게 3개를 잡아 주고

2번쨰를 기준으로 잡고 그것의 오른쪽에 있는 수들중 제일 큰 수

 

ex) 7 2 3 7 7 이 있으면

7 7 3 2 7 (2번째와 4번쨰 swap)

7 7 3 7 2 (2번째와 5번쨰 swap)

 

이렇게 2개를 잡아 주고

이렇게 5번째를 오면 멈춘다.

 

 

조건 2.

만약 n번째를 오는중에 (남은 교환 횟수%2) == 0이라면 최대 정답값을 비교해준다.

왜냐하면 남은 교환 횟수가 짝수번이 남았다면 어떻게 교환을 하던 그 수를 만들 수 있기 때문이다.

ex) 7 2 3 7 7 에 남은 swap 횟수가 2번 남았다라는것은 2번의 swap으로 7 2 3 7 7을 무조건 만들 수 있기 때문이다.

생각해보면 당연하다.

 

그리고 남은 교환횟수가 0이라면 더이상 swap 못하니간 return을 해준다.

 

조건 3.

만약 n번째 자리까지 다왔는데 (남은 교환 횟수%2) == 1이라면 

즉, 그리디하게 최대로 다 만들었는데 남은 교환 횟수가 홀수이면 맨 끝 2자리를 swap 한다.

 

ex) 4321 1 을 생각해보자.

이미 이 수는 최대지만 무조건 1번은 swap 해야 한다.

그러면 그나마 제일 손해가 적게 맨 끝 2자리를 swap 해야 한다.

 

 

 

그래서 만들었다. 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class Solution {
 
    static int max;
    static int len;
    static char[] strs;
    
    
    static void swap(int a, int b) {
        char tmp = strs[a];
        strs[a] = strs[b];
        strs[b] = tmp;
    }
    
    static void go(int change_pos, int cnt) {
 
        if(cnt%2 == 0)
            max = Math.max(max, Integer.parseInt(new String(strs)));
        
        if(cnt == 0) {
            return;
        }
        
        if(change_pos == len-1) {
            if(cnt%2 == 1) {
                swap(len-2, len-1);
                max = Math.max(max, Integer.parseInt(new String(strs)));
                swap(len-2, len-1);
            }
            return;
        }
        
        int max_num = strs[change_pos] - '0';
        
        for(int i = change_pos+1 ; i < len ; i++)
            max_num = Math.max(max_num, strs[i] -'0');
        
        if(max_num == strs[change_pos] - '0')
            go(change_pos+1, cnt);
        else {
            for(int i = change_pos+1 ; i < len ; i++) {
                if(max_num == strs[i] - '0') {
                    swap(i, change_pos);
                    go(change_pos+1 , cnt-1);
                    swap(i, change_pos);
                }
            }
        }
 
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int z = 1 ; z <= tc ; z++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int change = Integer.parseInt(st.nextToken());
            strs = str.toCharArray();
            len = str.length();
            //String swappedString = new String(c);
        
            max = 0;
            
            go(0, change);
            System.out.println("#"+z+" "+max);
        }
        
        
    }
}

하지만 틀렸다.

 

않이 왜??????????????????

 

36~48번째줄을 잘못 만들었다.

 

반례는 77732 1 이였다.

기존 생각으로 짜면

첫번째 자리를 기준으로 swap 기준을 잡아보자.

수정 전에는 7보다 큰 수가 없으니깐 그냥 첫번째 자리는 swap없이 넘어갈 것이고

2번째도 3번째 4번째 5번째 다 없으니깐 

5번째까지 swap 횟수를 소비하지 않을 것이고

조건 3에 의해서 

77723이라는 답을 뱉을 것이다.

BUT... 77732 1 의 답은 77732이다. 오우 쒰!!!!!!!! (1,2번째 swap하면 된다.)

 

그래서 7보다 큰 수 -> 7보다 크거나 같은 수를 구하도록 바꿨다.

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210331_SWEA1244 {
 
    static int max;
    static int len;
    static char[] strs;
    
    
    static void swap(int a, int b) {
        char tmp = strs[a];
        strs[a] = strs[b];
        strs[b] = tmp;
    }
    
    static void go(int change_pos, int cnt) {
 
        if(cnt%2 == 0)
            max = Math.max(max, Integer.parseInt(new String(strs)));
        
        if(cnt == 0) {
            return;
        }
        
        if(change_pos == len-1) {
            if(cnt%2 == 1) {
                swap(len-2, len-1);
                max = Math.max(max, Integer.parseInt(new String(strs)));
                swap(len-2, len-1);
            }
            return;
        }
 
        go(change_pos+1, cnt);
        
        int max_num = strs[change_pos] - '0';
        for(int i = change_pos+1 ; i < len ; i++) {
            if(max_num <= strs[i] - '0') {
                swap(i, change_pos);
                go(change_pos+1 , cnt-1);
                swap(i, change_pos);
            }
        }
            
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int z = 1 ; z <= tc ; z++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int change = Integer.parseInt(st.nextToken());
            strs = str.toCharArray();
            len = str.length();
            //String swappedString = new String(c);
        
            max = 0;
            
            go(0, change);
            System.out.println("#"+z+" "+max);
        }
        
        
    }
}

 

그러니깐 정답을 뱉는다....

 

여윽시 뻑킹그리디다.