[백준, Java] 20952번, 게임 개발자 승희(정수론)

문제 링크

20952번: 게임 개발자 승희

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 71421게임의 규칙은 문제의 연산을 M번 진행합니다. 

2. 연산을 진행할 때 모든 수열의 값의 7의 배수이면 해당 연산은 수행하지 않습니다.

3. M번 연산이 끝난 뒤, 수열의 정보를 결과로 출력합니다.

4. 수열의 정보를 출력할 때에는 1000000007으로 나눈 나머지 값을 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. M번의 연산을 진행할 수 있는 수열의 값들을 찾아서 연산을 진행합니다.

 

3. 연산을 진행한 뒤 수열의 값들을 결과로 출력합니다.

 

 

71421 게임 진행

 

71421게임의 핵심적인 내용은 7의 배수가 되면 해당 수열의 값을 제거한다는 것입니다.

 

즉, 나머지를 이용해서 7의 배수가 되는지 확인합니다.

 

7으로 나눈 나머지를 구할 때 나올 수 있는 값은

 

{0, 1, 2, 3, 4, 5, 6}이며, 0일 때에는 7의 배수가 됩니다.

 

A 수열의 어떤 수가 나오든 나올 수 있는 정보는 나머지 {0, 1, 2, 3, 4, 5, 6}을 가지는 정수들이 몇 개인지 입니다.

→ 어떤 수가 나오든 B의 수열을 더했을 때 7의 배수가 되느냐 안되느냐가 중요하기 때문이다.

 

나머지가 3인 값과 나머지가 4인 값을 합(3 + 4 = 7)이 7이 된다는 것은?? 

→ 해당 값이 7의 배수가 된다는 것입니다.

 

위 방법을 사용하여 시작 나머지 값이 {0, 1, 2, 3, 4, 5, 6}일 때 7의 배수가 되는지 M번을 연산해봅니다.

 

0	1	2	3	4	5	6
0	1	2	3	4	5	6

 

 

여기서 B[0]의 값이 32이면??

 

→나머지는 32 mod 7 = 4

 

나머지끼리 더하면?

 

0	1	2	3	4	5	6
4	5	6	7	1(8 mod 7)	2 (9 mod 7)	3 (10mod 7)

 

즉, 시작값의 나머지가 3이면 해당 값은 7의 배수가 되는 경우가 존재하므로, 해당 정수는 결과 수열에 포함될 수 없습니다.

 

위 과정을 반복하면서 하나의 경우를 고려해야 합니다.

 

→ 모든 수가 7의 배수가 되서 연산이 진행되지 않는 경우

 

위 경우를 비교하기 위해서 A수열의 나머지가 {0, 1, 2, 3, 4, 5, 6}의 정수 개수를 구합니다.

 

이후, 위와 같이 시작값의 나머지가 3인 값이 전체 정수의 개수이면 모든 수가 7의 배수가 되는 것을 알 수 있습니다.

 

위 2가지 방법을 이용해서 구현하였습니다.

 

 

※ 예제입력을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 7

 

M : 3

 

수열 인덱스	0	1	2	3	4	5	6
현재 나머지	0	1	2	3	4	5	6
개수	1(7)	1(1)	1(2)	1(3)	1(4)	1(5)	1(6)

 

B[] = {1, 2, 3}

 

2. M번의 연산을 진행할 수 있는 수열의 값들을 찾아서 연산을 진행합니다.

 

B[0]번째 연산 진행

 

1 mod 7 = 1

 

수열 인덱스	0	1	2	3	4	5	6
현재 나머지	1	2	3	4	5	6	0
개수	1(7)	1(1)	1(2)	1(3)	1(4)	1(5)	1(6)

 

시작 나머지가 6인 값은 결과 수열에 포함될 수 없습니다.

 

또한, 남아 있는 수를 확인하였을 때 해당 나머지를 가지는 개수가 모든 수열의 개수가 아니기 때문에

 

연산으로 모든 수가 7의 배수가 되지 않습니다.

 

 

B[1]번째 연산 진행

 

2 mod 7 = 2

 

수열 인덱스	0	1	2	3	4	5	6
현재 나머지	3	4	5	6	0	1	0
개수	1(7)	1(1)	1(2)	1(3)	1(4)	1(5)	1(6)

 

시작 나머지가 4인 값은 결과 수열에 포함될 수 없습니다.

 

또한, 남아 있는 수를 확인하였을 때 해당 나머지를 가지는 개수가 모든 수열의 개수가 아니기 때문에

 

연산으로 모든 수가 7의 배수가 되지 않습니다.

 

B[2]번째 연산 진행

 

3 mod 7 = 3

 

수열 인덱스	0	1	2	3	4	5	6
현재 나머지	6	0	1	2	0	4	0
개수	1(7)	1(1)	1(2)	1(3)	1(4)	1(5)	1(6)

 

시작 나머지가 1인 값은 결과 수열에 포함될 수 없습니다.

 

또한, 남아 있는 수를 확인하였을 때 해당 나머지를 가지는 개수가 모든 수열의 개수가 아니기 때문에

 

연산으로 모든 수가 7의 배수가 되지 않습니다.

 

 

남아 있는 수들은 B수열의 모든 값의 연산이 작용했기 때문에 sum(B) = 1 + 2 + 3 = 6을 결과를 모두 더합니다.

 

수	1	2 + 6 = 8	3 + 6 = 9	4	5 + 6 = 11	6	7 + 6 = 13
나머지	1(X)	2	3	4 (X)	5	6 (X)	0

 

 

 

3. 연산을 진행한 뒤 수열의 값들을 결과로 출력합니다.

수열의 크기 : 4

 

남은 수열 정보

 

8

9

11

13

 

 

4

4 2 3 1을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N, M, 수열의 정보를 띄어쓰기 기준 구분합니다.
• 나머지를 이용한 M번 연산을 통해 초기 나머지 값이 결과로 출력 가능한지 확인합니다.
• 출력 가능한 수열의 값에 대해서 B_SUM을 더한 값들을 BufferedWritetr 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    //나누고 나머지를 구할 값
    static final int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        int[] B = new int[M];
        st = new StringTokenizer(br.readLine()," ");
        long B_SUM = 0;
        int[] cntA = new int[7];
        //A수열 저장 및 나머지 {0, 1, 2, 3, 4, 5, 6}을 가지는 정수 개수 구하기
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
            cntA[A[i]%7]++;	//나머지 정수 개수 구하기
        }
        st = new StringTokenizer(br.readLine()," ");
        //B수열 저장
        for(int i=0;i<M;i++){
            B[i] = Integer.parseInt(st.nextToken());
        }
        StringBuilder sb = new StringBuilder();
        boolean[] disable = new boolean[7];
        int[] check = new int[7];
        //나머지값 초기화
        for(int i=1;i<7;i++){
            check[i] = i;
        }
        //M번 연산을 진행
        for(int i=0;i<M;i++){
            //현재 상태 COPY 형성
            int[] copyCnt = new int[7];
            int[] copyCheck = new int[7];
            boolean[] copyDisable = new boolean[7];
            for(int j=0;j<7;j++){
                copyCnt[j] = cntA[j];
                copyCheck[j] = check[j];
                copyDisable[j] = disable[j];
            }
            //현재 B의 나머지 값 구하기
            int temp = B[i] % 7;
            //나머지값 더하기
            for(int j=0;j<7;j++){
                if(copyDisable[j]){
                    continue;
                }
                copyCheck[j] = (copyCheck[j] + temp) % 7;
                //7의 배수가 되었을 때
                if(copyCheck[j] == 0){
                    copyDisable[j] = true;
                    copyCnt[j] = 0;
                }
            }
            int sum = 0;
            //해당하는 나머지가 현재 존재하는 모든 정수인지 확인하기 위한 합 구하기
            for(int j=0;j<7;j++){
                sum += copyCnt[j];
            }
            //sum != 0이면 해당 나머지는 현재 존재하는 모든 정수가 아니다!
            if(sum != 0){
                //해당 연산 진행되었으므로, B_SUM의 더하기
                B_SUM = (B_SUM + B[i]) % MOD;
                //COPY이 진짜가 되도록 설정
                for(int j=0;j<7;j++){
                    cntA[j] = copyCnt[j];
                    check[j] = copyCheck[j];
                    disable[j] = copyDisable[j];
                }
            }
        }
        //연산이 종료된 뒤 나올 수 있는 수열의 정보 StringBuilder 저장
        List<Long> list = new ArrayList<>();
        for(int i=0;i<N;i++){
                if(!disable[A[i]%7]){
                    list.add((A[i] + B_SUM % MOD) % MOD);
                }
            }
            sb.append(list.size()).append("\n");
            for(int i=0;i<list.size();i++){
                sb.append(list.get(i)).append(" ");
            }
        //저장된 결과 BufferedWriter 저장
        bw.write(sb.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}