[백준] 15721번: 번데기 (Java)

1. 문제설명

n-1 회차일 때 ‘뻔 – 데기 – 뻔 – 데기 – 뻔(x n번) – 데기(x n번)’ 문장으로 진행되는 번데기 게임이 있다.

플레이어는 원을 반시계 방향으로 돌아 계속 진행할 수 있다.

T번째로 ‘뻔’ 또는 ‘데기’를 외치는 사람이 원에서 몇 번째 사람인지 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 무한 루프(while)를 사용해 게임을 진행한다.
• 각 라운드마다 "뻔 – 데기 – 뻔 – 데기" 패턴을 먼저 처리한다.
• 다음으로 “뻔”을 `round+1` 번, “데기”를 `round+1` 번 반복한다.
• 매번 “뻔” 또는 “데기”의 `count`를 증가시키고, T번째 발생을 체크한다.
• 원형으로 앉은 것을 고려해 사람 번호를 `person % A` 로 계산한다.

 

3. 틀린 이유 설명

• 처음 문제를 이해할 때 n번 반복하는 “뻔”이나 “데기”를
  해당 순서에 해당하는 한 사람이 말하는 것으로 잘못 이해하여 다르게 풀이하였다.
• T번째 발생을 찾지 못하고, 단순히 T번 반복 수행했다.
• 라운드가 진행됨에 따라 “뻔”과 “데기”의 반복 횟수가 증가하는 것을 구현하지 못했다.

int[] game = new int[6];
    int person = 0;
    for(int i=0; i<T; i++) {
        for(int j=0; j<6; j++) {
            game[j] = person % A; // 0 ~ A-1 반복하여 저장
            person++;
        }
    }

    if(C == 0) System.out.println(game[4]);
    else if(C == 1) System.out.println(game[5]);
}

 

4. 올바른 접근 방식 및 해결 방식

• 게임의 진행을 무한 루프로 구현해야 한다.
• 각 라운드마다 “뻔”과 “데기”의 횟수가 증가하는 패턴을 구현해야 한다.
• “뻔”과 “데기”의 count를 별도로 증가시켜 T번째 발생을 찾을 수 있다.
• 각 라운드마다 "뻔"과 "데기"의 반복 횟수가 1씩 증가하는 점을 구현해야 한다.

 

5. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine()); // 사람 수
        int T = Integer.parseInt(br.readLine()); // 구하고자 하는 "뻔"과 "데기"의 순서
        int C = Integer.parseInt(br.readLine()); // 0이면 "뻔", 1이면 "데기"

        int person = 0; // 현재 순서의 사람 (0부터)
        int count = 0; // 현재까지 발생한 "뻔" 또는 "데기"의 횟수
        int round = 1; // 현재 라운드 (1부터)

        while(true) {
            // "뻔 – 데기 – 뻔 – 데기" 패턴
            for(int i=0; i<4; i++) {
                // 현재 순서가 "뻔"인지 "데기"인지 확인
                // 원하는 구호이고 T번째 발생했을 때
                if(i%2 == C && ++count == T) {
                    System.out.println(person % A); // T번째 발생 시 현재 사람 번호 출력
                    return;
                }
                person++; // 다음 사람
            }

            // "뻔" round+1 번 반복
            for(int i=0; i<round+1; i++) {
                if(C == 0 && ++count == T) { // "뻔"을 찾는 경우이고 T번째 발생했을 때
                    System.out.println(person % A);
                    return;
                }
                person++;
            }

            // "데기" round+1 번 반복
            for(int i=0; i<round+1; i++) {
                if(C == 1 && ++count == T) { // "데기"을 찾는 경우이고 T번째 발생했을 때
                    System.out.println(person % A);
                    return;
                }
                person++;
            }

            round++; // 다음 라운드 (반복 횟수 증가)
        }
    }
}