[백준 20952] 게임 개발자 승희 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/20952

 

문제

승희는 최근 369 게임에 푹 빠졌다. 369 게임을 하던 승희는 놀라 자빠질 수밖에 없었다. 369 게임을 잘하는 자기 자신이 너무 대견하였기 때문이다. 369 게임이 식상해진 승희는 369 게임을 변형한 71421 게임을 개발하였다. 369 게임에서는 3, 6, 9가 들어가는 수에 손뼉을 치지만, 71421 게임에서는 7의 배수에 손뼉을 친다. 승희는 71421 게임을 널리 퍼트리기로 결심하였다.

71421 게임은 최근 대학생들 사이에서 큰 인기를 끌고 있다. 369 게임에 이어 71421 게임도 식상해진 승희는 수열을 이용한 새로운 게임을 개발하였다.

승희의 수열 게임은 혼자서 즐길 수 있는 재미난 게임이다. 시작하기에 앞서 길이가 N인 수열 A와 길이가 M인 수열 B를 준비한다. 이후 수열 A에 대하여 M번의 연산을 수행한다. i(1 ≤ i ≤ M)번째 연산은 수열 A의 모든 원소에 Bi를 더한 후 7의 배수인 원소들을 제거하는 연산이다. 단, 연산을 수행한 결과 수열 A의 모든 원소가 제거된다면 해당 연산은 수행하지 않는다.

수열 A와 B가 주어졌을 때, M번의 연산을 수행한 결과를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수열 A의 길이 N과 수열 B의 길이 M이 주어진다.

두 번째 줄에 N개의 정수 A1, A2, ..., AN이 주어진다.

세 번째 줄에 M개의 정수 B1, B2, ..., BM이 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

 

출력

첫 번째 줄에 M번의 연산을 수행한 후 수열 A의 길이 K를 출력한다.

두 번째 줄에 K개의 정수 A1, A2, ..., AK를 공백으로 구분하여 출력한다. 답이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

풀이

접근법

1. 완전탐색으로 하면 100000x100000 이므로 다른 방법을 사용해야 한다.
2. 7의 배수로 묶여서, 어느 숫자를 더해도 항상 같은 단위로 더해지니까, 초기 값을 7로 나눈 나머지가 인덱스인, 크기가 7인 배열을 생성하자.
3. 또한 문제에서 모든 원소가 제거가 되면 해당 연산은 건너 뛰니까, 해당 인덱스에 몇개가 남아있는지 기록하는 배열도 생성하자.
4. 0부터 시작하여 B를 돌면서 해당 인덱스의 값이 삭제가 될 수 있는지 확인하자. 이 때 이미 삭제가 되었다면 그냥 더해주고, 삭제가 되지 않았다면 모든 원소가 제거가 될 수 있는지 확인한 후, 제거가 안된다면 해당 인덱스를 제거처리하자.
5. 남은 수는 B를 돌면서 해당 인덱스가 제거가 되었는지 확인한 후, 제거가 되지 않았다면 +sum 을 하여 연산 수행 결과를 구하자.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int MOD = 1000000007;
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        int[] brr = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) brr[i] = Integer.parseInt(st.nextToken());
        boolean[] removed = new boolean[7];
        int[] prefix = new int[7];
        for(int i=0;i<N;i++) prefix[(7-arr[i]%7)%7]++;
        int remain = N;
        int sum = 0;
        int idx = 0;
        for(int i=0;i<M;i++) {
            int newIdx = (brr[i] + idx)%7;
            if (prefix[newIdx] == remain) continue;
            idx = newIdx;
            sum += brr[i];
            sum%=MOD;
            if (!removed[newIdx]) remain -= prefix[newIdx];
            removed[newIdx] = true;
        }
        int ans = 0 ;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++) {
            if (!removed[(7-arr[i]%7)%7]) {
                ans++;
                sb.append((arr[i]+sum)%MOD).append(" ");
            }
        }
        System.out.println(ans);
        System.out.println(sb);
    }
}