문제 : boj28706
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
필요 알고리즘
- DP (동적 계획법)
- DP로 해결 가능한 문제이다. 이하 풀이는 bit DP (비트필드를 이용한 다이나믹 프로그래밍)로 풀었다.
※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.
풀이
모든 경우의 수를 본다고 해보자. 1부터 시작해서 차례차례 경우의 수를늘려가는거다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
이러면 당연히 2^200000의 경우의 수가 존재하므로 너무나 천문학적인 수치이다. 그럼 어떻게 해야할까? 이 문제에서 결과적으로 알아야 하는 것은 'K가 7의 배수냐?' 이다. 바꿔 말하면 7로 나눈 나머지가 0이 되게 가능하냐이다. 그리고 나머지 연산에는 다음과 같은 성질이 있다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
즉, 최종적으로 7로 나눈 나머지가 0이 되냐를 알고싶은거라면 중간 연산 시 7로 나눈 나머지만 유지해도 결과를 아는데 문제가 없다. 아래처럼 7로 나눈 나머지만 유지해보자.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
그러고보면 빨간 글자들이 1, 2, 0, 1 이다. 1이 중복된다! 그리고 비둘기집의 원리에 따라 최종적으로 2^200000 개의 비둘기들은 비둘기집 7개에 들어가야 하고(7로 나눈 나머지만 유지할 것이므로), 비둘기의 수는 중요하지 않다. 즉 위에서 1이 두 번 나온건 의미가 없다. 아무튼 저 빨간 글자들 중 0, 1, 2가 존재했는지만 알면 된다. 따라서 아래처럼 2^N개의 정점이 아니라 그냥 각 층별로 7개짜리 배열로 충분하다. 이 경우 dp[N][7] 이면 된다.
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
근데 어차피 존재하냐, 안하냐이니 1과 0으로 표현 가능하고, 7개만 알면 된다. 따라서 그냥 정수 하나에 bit를 가지고 표현할 수도 있다. 이 경우 dp[N] 으로 끝난다(사실 직전 데이터가 있으면 되서 굳이 배열 안만들어도 되긴한다.). 아래 이미지에선 설명의 편의를 위해 배열 형태 그대로 2진수로 표현했는데, 코드에선 사실 우측부터 0,1,2,3... 을 표현하는게 편하다보니 아래 그림의 0100000은 코드에서 0000010 으로 표현된다.
![](https://blog.kakaocdn.net/dn/ESISY/btsAPIbEN06/b4qiFYe2w2dphkztnNl8J0/img.png)
최종적으로 마지막에 연산된 정수값에서 '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;
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 2190 - 점 고르기 2 (java) (0) | 2023.11.25 |
---|---|
[자바] 백준 22956 - 소나기 (java) (2) | 2023.11.24 |
[자바] 백준 23040 - 누텔라 트리 (Easy) (java) (0) | 2023.11.22 |
[자바] 백준 11108 - TV 전쟁 (java) (0) | 2023.11.21 |
[자바] 백준 29730 - 임스의 데일리 인증 스터디 (java) (0) | 2023.11.21 |
댓글