[SWEA] 1244 최대상금

쉬운줄알았는데 좀 고민하게 해준 문제다

먼저 비슷만 문제는 백준의 숨바꼭질 5(https://sejinik.tistory.com/194)다 

 

이 문제는 모든 경우를 DFS로 다 해보면 답이 나오지만

그냥 하면 시간초과 난다

 

그럼 시간을 줄이기 위해서 어떻게 해야할까?

한번 생각해보자

내가 홀수일때 방문한곳은 다음 홀수에도 방문할 수 있다

반대로 짝수도 마찬가지다

예를들어 123-213-123 이런식으로 2차이나면 원래자리로 다시 돌아올 수 있다

 

그럼 우리는 방문할 수 있는 숫자 중에서 홀,짝으로 나눠서 방문했는지 체크를 해보면 된다!

내가 만약 다음 방문할 곳에 홀수번만에 갈 때 이전에 홀수번에서 방문했다면 방문하지않는다!

아니라면 방문하면된다!!

 

그럼 시간안에 dfs를 통해 답을 찾아갈 수 있다!

 

소스코드

import java.util.Scanner;
 
public class Solution {
    public static int[] arr;
    public static int k,ans;
    public static boolean[][] check = new boolean[1000010][2];
    public static void swap(int x,int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y]=temp;
    }
    public static int num() {
        int ret=0;
        for(int i=0;i<arr.length;i++) {
            ret*=10; ret+=arr[i];
        }
        return ret;
    }
    public static void solve(int cnt) {
        check[num()][cnt%2]=true;
        if(cnt==k) {
            ans = Math.max(ans, num()); return;
        }
        
        for(int i=0;i<arr.length;i++) {
            for(int j=0;j<arr.length;j++) {
                if(i==j) continue;
                swap(i,j);
                if(!check[num()][(cnt+1)%2]) solve(cnt+1);
                swap(i,j);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int tc=1;tc<=t;tc++) {
            String s = sc.next(); k=sc.nextInt();
            char[] ca = s.toCharArray();
            arr = new int[ca.length];
            
            for(int i=0;i<ca.length;i++) arr[i]=ca[i]-'0';
            ans=num();
            solve(0);
            System.out.println("#"+tc+" "+ans);
        }
    }
}