[백준 C++] 28706번 럭키 세븐

28706번: 럭키 세븐

문제 요약

문제

당신은 양의 정수 $K$를 하나 가지고 있습니다. 처음에 $K=1$입니다. 당신에게는 $N$개의 턴이 주어지고, 각 턴에는 $2$개의 선택지 중 하나를 골라야합니다. 각각의 선택지는 “+ $v$ ” 혹은 “* $v$ ”와 같은 방식으로 주어집니다. $(1 \le v \le 9)$ 

• “+ $v$ ”: $K$를 $K + v$로 바꿉니다.
• “* $v$ ”: $K$를 $K \times v$로 바꿉니다.

선택지를 모두 고른 이후 결과로 나온 $K$가 $7$의 배수가 되도록 할 수 있나요?

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1 \le T \le 10\,000)$  각 테스트케이스의 첫 줄에 턴의 수 $N$이 주어집니다. $(1 \le N \le 200\,000)$  다음 $N$개의 줄의 $i$번째 줄은 “ $op_1$ $v_1$ $op_2$ $v_2$ ”와 같은 방식으로 모든 문자를 공백으로 구분하여 주어집니다. $op_1$과 $op_2$는 ‘+’ 혹은 ‘*’이며, $v_1$과 $v_2$는 $1$ 이상 $9$ 이하의 정수입니다. 이는 $i$번째 턴의 선택지가 “ $op_1$ $v_1$ ”과 “ $op_2$ $v_2$ ”라는 것을 의미합니다. 모든 테스트케이스에서 $N$의 합이 $200\,000$을 넘지 않습니다.
• 출력: 각 테스트케이스마다 한 줄에 하나씩, $K$를 $7$의 배수로 만들 수 있다면 “LUCKY”, 불가능하다면 “UNLUCKY”를 출력하세요. ``` 예제1

입력 3 1

• 3 + 6 2
• 3 + 6
• 1 + 2 5
• 3 * 1
• 4 + 5
• 9 * 2
• 6 + 3
• 5 + 5 출력 LUCKY UNLUCKY LUCKY ```

  풀이

  이 문제는 7로 나눈 나머지가 0~6까지 총 7가지뿐이라는 점을 활용하는 DP 문제다. 모든 수식을 직접 계산해 나가는 게 아니라, 나머지가 같은 경우만 추적하면 되기 때문에 상태 수를 줄일 수 있다. 즉, 특정 시점에서 나머지가 동일하다면, 그 이후의 선택은 중복되므로 같은 상태로 처리할 수 있다. DP 배열은 dp[i][r] = true/false 형식으로 구성해서,

• i번째 줄까지 처리했을 때,
• 나머지가 r인 경우가 가능한지 여부를 저장한다. 각 줄마다 연산이 두 가지(+, *)가 주어지고, 현재 가능한 나머지 상태들로부터 두 연산 결과에 해당하는 새로운 나머지를 갱신해 나간다. 모든 줄을 처리한 후 dp[n][0]이 true라면, 7로 나누어 떨어지는 경우가 존재한다는 뜻이다. 이처럼 모든 수식을 실제로 계산하는 대신 나머지 상태만 관리하면 효율적으로 풀 수 있는 문제다.

어려웠던 점

나머지를 확인한다는 아이디어가 살짝 힘들었다.

배운 점 / 느낀 점

없다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;
    for(int _ = 0; _ < T; _++){
        cin >> n;
        int v1, v2;
        char op1, op2;
        vector<vector<bool>> a(n+1, vector<bool>(7, false));
        a[0][1] = true;
        for(int i = 1; i <= n; i++){
            cin >> op1 >> v1 >> op2 >> v2;
            for(int j = 0; j < 7; j++){
                if(!a[i-1][j]){
                    continue;
                }
                if(op1 == '+'){
                    a[i][(j+v1)%7] = true;
                }
                else{
                    a[i][(j*v1)%7] = true;
                }
                if(op2 == '+'){
                    a[i][(j+v2)%7] = true;
                }
                else{
                    a[i][(j*v2)%7] = true;
                }
            }
        }
        if(a[n][0]){
            cout << "LUCKY\n";
        }
        else{
            cout << "UNLUCKY\n";
        }
    }

    return 0;
}