[백준] 1592번: 영식이와 친구들(구현, 수학, 시뮬레이션)

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

1592번: 영식이와 친구들

코드

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 bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		/*
		 * 1 ~ N까지 시계방향으로 앉는다.
		 * 공을 던지며 반복하고, 한 사람이 공을 M번 받으면 게임이 종료(현재 받은 공도 포함)
		 * 공을 던질때, 현재 받은 횟수가 홀수 -> 시계방향으로 L번째 사람에게, 짝수 -> 반시계방향으로 L번째 사람에게 공던짐
		 */
		int N = Integer.parseInt(st.nextToken());	
		int M = Integer.parseInt(st.nextToken());	
		int L = Integer.parseInt(st.nextToken());	
		int ballCount = 0;
		int[] arr = new int[N+1];
		int index = 1;
		arr[1] = 1;	// 현재 공 포함하므로 첫 번째 사람 +1
		
		while(true) {
			// 현재 받은 사람이 홀수번 받았을 경우 -> 시계방향(index + L)
			// 현재 받은 사람이 짝수번 받았을 경우 -> 반시계(index - L)
			index = (arr[index] % 2 == 1) ? (index + L) : index - L; 
			
			// 다음 받을 사람이 배열의 범위 벗어났을 때(시계 방향일 때)
			if(index > N) 
				// 인원만큼 나눈 나머지가 다음에 받는 사람임
				// index = 7, N = 5 이면 다음엔 2번째 사람이 받음.
				index %= N;	
			
			// 다음 받을 사람이 배열의 범위 벗어났을 때(반시계 방향일 때)
			else if(index < 1) 
				// 1번이 반시계방향으로 4번에게 줘야할때 -> (-1) + 5 = 4
				index += N;
			
			arr[index] ++;	// 공 받는 사람 ++
			ballCount ++;	// 공 던진 횟수 ++
			
			// 한 사람이 공을 M번 받으면 종료
			if(arr[index] == M)
				break;
		}
		
		System.out.println(ballCount);
		bf.close();
	}

}

문제이해

문제를 푸는데 좀 걸렸다 ...

일단 조건은 아래와 같다.

 

1. 1 ~ N까지 원형으로 시계방향으로 앉아있고,

2. 1번 사람부터 현재 공을 받은 횟수가 홀수이면 시계 방향으로 L번째 있는 사람에게,

3. 현재 공을 받은 횟수가 짝수이면 반시계 방향으로 L번째 있는사람에게 공을 던진다.

4. 한 사람이 공을 M번 받으면 게임은 끝난다.(지금 받은 공도 포함하여 센다.)

 

풀이

현재 1번에게 공이 있고, 이 공도 받은공으로 포함하므로 첫 번째 사람은 +1로 설정한다.

 

* 현재 공을 받은 사람이 받은 횟수가 홀수일 경우 -> 시계방향이므로 +L

* 현재 공을 받은 사람이 받은 횟숙가 짝수일 경우 -> 반시계방향이므로 -L을 해준다.

* 배열 범위를 벗어날 경우를 생각해야 한다.(1 ~ N까지 이므로 N보다 크거나, 1보다 작을때)

* 위 범위에 맞게 조건을 설정하고, 다음 받는 사람의 index를 구한다.

* 기타 설명은 주석.