[자바] 백준 28706 - 럭키 세븐 (java)

목차

문제 : boj28706

 

 

필요 알고리즘

• DP (동적 계획법)
  
  • DP로 해결 가능한 문제이다. 이하 풀이는 bit DP (비트필드를 이용한 다이나믹 프로그래밍)로 풀었다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  모든 경우의 수를 본다고 해보자. 1부터 시작해서 차례차례 경우의 수를늘려가는거다.

 

 

  이러면 당연히 2^200000의 경우의 수가 존재하므로 너무나 천문학적인 수치이다. 그럼 어떻게 해야할까? 이 문제에서 결과적으로 알아야 하는 것은 'K가 7의 배수냐?' 이다. 바꿔 말하면 7로 나눈 나머지가 0이 되게 가능하냐이다. 그리고 나머지 연산에는 다음과 같은 성질이 있다.

 

 

  즉, 최종적으로 7로 나눈 나머지가 0이 되냐를 알고싶은거라면 중간 연산 시 7로 나눈 나머지만 유지해도 결과를 아는데 문제가 없다. 아래처럼 7로 나눈 나머지만 유지해보자.

 

 

  그러고보면 빨간 글자들이 1, 2, 0, 1 이다. 1이 중복된다! 그리고 비둘기집의 원리에 따라 최종적으로 2^200000 개의 비둘기들은 비둘기집 7개에 들어가야 하고(7로 나눈 나머지만 유지할 것이므로), 비둘기의 수는 중요하지 않다. 즉 위에서 1이 두 번 나온건 의미가 없다. 아무튼 저 빨간 글자들 중 0, 1, 2가 존재했는지만 알면 된다. 따라서 아래처럼 2^N개의 정점이 아니라 그냥 각 층별로 7개짜리 배열로 충분하다. 이 경우 dp[N][7] 이면 된다.

 

 

  근데 어차피 존재하냐, 안하냐이니 1과 0으로 표현 가능하고, 7개만 알면 된다. 따라서 그냥 정수 하나에 bit를 가지고 표현할 수도 있다. 이 경우 dp[N] 으로 끝난다(사실 직전 데이터가 있으면 되서 굳이 배열 안만들어도 되긴한다.). 아래 이미지에선 설명의 편의를 위해 배열 형태 그대로 2진수로 표현했는데, 코드에선 사실 우측부터 0,1,2,3... 을 표현하는게 편하다보니 아래 그림의 0100000은 코드에서 0000010 으로 표현된다.

 

 

   최종적으로 마지막에 연산된 정수값에서 '0'이라는 비둘기집이 1이면 LUCKY를 출력해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            int n = Integer.parseInt(br.readLine());

            int[] dp = new int[n+1];
            dp[0] = 1<<1;

            for (int i = 1; i <= n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int op1 = st.nextToken().charAt(0) == '+' ? 0 : 1;
                int num1 = Integer.parseInt(st.nextToken());
                int op2 = st.nextToken().charAt(0) == '+' ? 0 : 1;
                int num2 = Integer.parseInt(st.nextToken());

                dp[i] = proc(dp[i-1], op1, num1, op2, num2);
            }

            sb.append((dp[n]&1)==1 ? "LUCKY" : "UNLUCKY").append('\n');
        }
        System.out.print(sb);
    }

    private int proc(final int bf, final int op1, final int num1, final int op2, final int num2) {
        int result = 0;
        for (int i = 0; i <= 6; i++) {
            if ((bf&(1<<i)) == 0) continue;

            int tmp = i;
            if (op1 == 0) tmp+=num1;
            else tmp*=num1;
            result |= 1<<(tmp%7);

            tmp = i;
            if (op2 == 0) tmp+=num2;
            else tmp*=num2;
            result |= 1<<(tmp%7);
        }
        return result;
    }
}