[자바] 백준 25194 - 결전의 금요일 (boj java)

문제 : boj25194

 

  우선 문제를 이해했다면, N개의 정수에서 1~N개를 더한 여러 경우의 수 중 7로 나눈 나머지가 4가 되는 경우가 있는지 찾는 문제라고 이해할 수 있다. 하지만 이걸 구하는 방법을 찾긴 좀 어려웠다. 단순히 찾아보면 O(1000!) 이기 때문에 말도 안되는 경우의 수가 나오기 때문이다.

 

  내 기본 아이디어는 나머지 연산의 분배법칙을 활용하는 것이었다. 나머지 연산의 경우 다음의 분배법칙을 따른다.

  즉, 100000이하의 큰 'A일'들이 입력으로 들어오지만, 결국 그냥 미리 7로 나눠놔도 결과를 구하는데에 지장이 없다는 얘기이다. 또한 7로 나눈 나머지가 0이 되는 경우는 아예 필요가 없는 경우이다(원점임). 따라서 버려준다. 그렇게 되면 이 문제는 1~6 까지의 숫자가 각각 여러개씩 존재하고, 그 1~6을 적절히 합친 값을 7로 나눠서 4가 나오는 경우를 찾는 문제가 된다.

 

  대회 중 푼거라 명확히 증명하고 풀진 못해서 너무 많이 연산하진 않도록 적당히 LIMIT을 대강 설정하고 제출했었는데 한방에 성공했다. 그렇게 짠 코드가 아래와 같다.

...
private static final int LIMIT = 100;
int[] cnt;
boolean chk = false;
private void dfs(int sum) {
    if (sum > LIMIT) return;
    if (sum%7==4) {
        chk = true;
        return;
    }
    for (int i = 1; !chk && i <= 6; i++) {
        if (cnt[i] == 0) continue;
        cnt[i]--;
        dfs(sum+i);
        cnt[i]++;
    }
}
private void solution() throws Exception {
    cnt = new int[7];
    int n = nextInt();
    while (n-->0) {
        int cur = nextInt();
        if (cur%7==0) continue;
        cnt[cur%7]++;
    }
    if (cnt[4] != 0) {
        System.out.println("YES");
        return;
    }
    dfs(0);
    System.out.println(chk?"YES":"NO");
}
...

 

 

  풀이를 쓰려고 생각해보니, 최악의 경우 O(6^(1000/6)) 라서 사실 통과할 수 없는 풀이였는데, 운이 좋았다. 왜냐면 잘 생각해보면 어차피 나머지가 0인 경우는 애초에 제외했었고, 그렇다면 그 이외 나머지가 1~6인 녀석들 6개만 있으면 어떻게든 나머지가 4인게 만들어진다. 결론은 위의 코드도 맞긴한데, 증명없이 맞은거고 아래 코드와 하는 일은 동일하다. 아래 코드는 카운팅한게 6개 이상이라면 그냥 바로 "YES"를 출력하고, 그렇지 않다면 처음에 짠 코드처럼 탐색해서 찾는 코드이다.

 

 

코드 : github

 int[] cnt;
    boolean chk = false;
    private void dfs(int sum) {
        if (sum%7==4) {
            chk = true;
            return;
        }
        for (int i = 1; !chk && i <= 6; i++) {
            if (cnt[i] == 0) continue;
            cnt[i]--;
            dfs(sum+i);
            cnt[i]++;
        }
    }
    private void solution() throws Exception {
        cnt = new int[7];
        int n = nextInt();
        int cntSum = 0;
        while (n-->0) {
            int cur = nextInt();
            if (cur%7==0) continue;
            cnt[cur%7]++;
            cntSum++;
        }
        if (cnt[4] != 0) {
            System.out.println("YES");
            return;
        }
        if (cntSum>=6) {
            System.out.println("YES");
            return;
        }
        dfs(0);
        System.out.println(chk?"YES":"NO");
    }