[BOJ] 27738 - 연산자 파티

문제

https://www.acmicpc.net/problem/27738

링크를 확인해보세요.

www.acmicpc.net

문제 정리

시간 제한	메모리 제한	정답 비율
2 초	512 MB	42.2%

요약

• 정수 N, A, B, C, D, E, F가 주어집니다.
• i가 1부터 N까지 1씩 증가할 때 X에 대하여 다음과 같이 연산을 수행합니다.
  • i % A == 0 -> X = X + i
  • i % B == 0 -> X = X % i
  • i % C == 0 -> X = X & i
  • i % D == 0 -> X = X ^ i (XOR)
  • i % E == 0 -> X = X | i
  • i % F == 0 -> X = X >> i
• 한 번에 여러 연산을 수행한다면 우선순위는 다음과 같습니다.
  • + > % > & > ^ > | > >>
• X의 초시값이 0입니다.
• i가 N이 되었을 때 최종 X를 구하시오.

입력 조건

• N : 1 ~ 1012
• A, B, C, D, E, F : 1 ~ 1,000,000

출력

최종 X값.

문제 풀이

N의 범위가 너무 커서 단순히 O(N)로는 문제를 해결할 수 없습니다. 따라서 위의 식에서 뭔가 압축할 수 있는 것이 있다고 생각하였습니다.

마지막 규칙을 다르게 표현하면 i % F == 0 -> X = X / 2i가 됩니다. 결국 마지막 규칙이 시행되는 시점에는 X는 항상 2i 보다 작으므로 X의 값이 0이 됩니다.

이를 이용하면 1부터 올라가면서 검색할 필요가 없어지게 됩니다. N 이하이면서 F의 배수인 가장 큰 수부터 탐색을 시작하면 됩니다.

여기서 최악의 상황일 때 N = 1012, F = 999001일 때로 약 107 번 연산을 하면 됩니다. 따라서 O(N)로 해결할 수 있게 됩니다.

풀이 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {

    void solve() throws Exception {
        // 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long C = Long.parseLong(st.nextToken());
        long D = Long.parseLong(st.nextToken());
        long E = Long.parseLong(st.nextToken());
        long F = Long.parseLong(st.nextToken());

        long start = (N / F) * F + 1;
        long X = 0;

        for (;start <= N; start++) {
            if (start % A == 0) {
                X += start;
            }
            if (start % B == 0) {
                X %= start;
            }
            if (start % C == 0) {
                X &= start;
            }
            if (start % D == 0) {
                X ^= start;
            }
            if (start % E == 0) {
                X |= start;
            }
        }

        System.out.println(X);
    }

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

회고

사실 문제는 쉬웠는데 문제 푸는 과정에서 놓친 부분이 너무 많아서 정리하게 되었습니다.

1. 최악의 입력 조건인 N = 1012, F = 999001에서 O(N)로 접근하여 틀렸다면, 틀린 이유는 성능(시간 초과)이 아닌 로직 오류로 판단했어야 합니다.
   • 초기에는 시간 초과로 틀렸다고 판단하여 Heap과 Set을 이용하여 배수 단위로 탐색 범위를 줄이는 방식으로 접근하였습니다.
2. F의 최댓값이 1,000,000이라는 것을 잊고 있었습니다.
   • TC를 설계할 때 N = 1012, A = 1, F = 1012 + 1 같은 극단적인 경우를 기준으로 판단하여, O(N)는 절대 안 된다는 잘못된 결론을 내렸습니다.
3. 오류가 발생한 지점이 무조건 실제 처리 로직에 있다고 확신하여 입력 및 초기화하는 부분을 확인하지 않았습니다.
   • 실제 오류가 발생한 이유는 long n = Integer.paseInt(br.readline())로 long을 int으로 파싱하면서 NumberFormatExceptoin이 발생하게 되어서 틀렸다고 표기된 것입니다.

최적화 하면서 작성한 코드

• 서브 태스크 1 기준으로는 그냥 단순히 반복문을 사용한 방식이 더 효율적이었습니다.
• 전체적으로는 입력값이 커질수록 해당 방식이 더 효율적이었습니다.

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.function.BiFunction;

class Main {

    void solve() throws Exception {
        // 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());

        long[] cmds = Arrays.stream(br.readLine().split(" "))
                .mapToLong(Long::parseLong).toArray();

        // 각 조건의 함수 등록.
        Map<Integer, BiFunction<Long, Long, Long>> funcs = new HashMap<>();
        funcs.put(0, this::A);
        funcs.put(1, this::B);
        funcs.put(2, this::C);
        funcs.put(3, this::D);
        funcs.put(4, this::E);
        funcs.put(5, this::F);

        Set<Long> visitSet = new HashSet<>();
        PriorityQueue<Long> minHeap = new PriorityQueue<>();

        // f의 최대 시작 위치를 fStart이라고 했을 때
        // 1 ~ fStart - 1 값을 얼마가 되든 fStart에 진입하면 X = 0 이 됨.
        // 따라서 실제 시작 위치가 fStart + 1이 됨.
        long start = (N / cmds[cmds.length - 1]) * cmds[cmds.length - 1] + 1;
        minHeap.add(start);
        visitSet.add(start);

        // a ~ e에 대하여 fStart 보다 크면서 N 보다 작은 수 구하기.
        for (int i = 0; i < cmds.length - 1; i++) {
            long c= cmds[i];
            long tmp = (start / c + 1) * c; // 최소 시작 지점.

            if (tmp <= N && !visitSet.contains(tmp)) {
                minHeap.add(tmp);
                visitSet.add(tmp);
            }
        }

        // X 탐색 시작.
        long X = 0;
        while(!minHeap.isEmpty()) {
            long now = minHeap.poll();

            for (int i = 0; i < cmds.length; i++) {
                if (now % cmds[i] == 0) {
                    X = funcs.get(i).apply(X, now);

                    long next = now + cmds[i];

                    if (next <= N && !visitSet.contains(next)) {
                        visitSet.add(next);
                        minHeap.add(next);
                    }

                }
            }
        }

        System.out.println(X);
    }

    private Long A(Long X, Long i) { return X + i; }
    private Long B(Long X, Long i) { return X % i; }
    private Long C(Long X, Long i) { return X & i; }
    private Long D(Long X, Long i) { return X ^ i; }
    private Long E(Long X, Long i) { return X | i; }
    private Long F(Long X, Long i) { return 0L; }

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