[BOJ] 12873 기념품 - java

제한

시간: 2초, 메모리: 512MB

참가자수 N : 1 ~ 5,000

→ O(N^2) 까지 가능하며, 완탐은 안되고, 시간 복잡도를 고려해야하는 문제임을 파악할 수 있다.

 

 

 

유형

Goal: 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하라

게임을 통해서 기념품을 받을 사람을 정하고, 그 게임은 정해진 규칙에 따라 진행하면된다.

→ 시뮬레이션 문제

 

 

 

Worst 시간복잡도

1. 한단계 씩 한 명씩 제거된다. → 4999번의 단계를 거쳐야한다.

2. 리스트 또는 배열의 원소를 하나씩 순회하는 방식은 약 5000^3번 순회해야하므로 TLE이다.

→ 순회없이 O(1)만에 다음 제거대상을 찾아야한다.

 

 

 

시뮬레이션 설계

1. 다음 제거대상을 찾는다.

2. 제거한다.

3. 게임 종료조건이면 종료한다.

 

 

다음 제거대상을 찾는 로직만 파악하면 끝나는 문제이다. 문제의 예시를 직접 그려보면 다음과 같은 식을 도출해낼 수 있다.

제거대상(BOJ 위치): (현재 BOJ 위치 + 현재단계^3 - 1) % 남은 사람 수

* 현재단계^3 계산 과정에서 Int overflow만 주의하자.

 

 

 

코드

public class Main {
	private static int N;
	private static List<Integer> people;

	public static void main(String[] args) throws IOException {
		input();
		game();
		System.out.println(people.get(0));
	}

	private static void game() {
		int bojIdx = 0;
		int stage = 1;
		while (!isEnd()) {
			bojIdx = getBojNextIdx(bojIdx, stage);
			people.remove(bojIdx);
			stage++;
		}
	}

	private static int getBojNextIdx(int curIdx, int stage) {
		return (int) ((curIdx + (long) Math.pow(stage, 3) - 1) % people.size());
	}

	private static boolean isEnd() {
		return people.size() == 1;
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		people = new LinkedList<Integer>();
		for (int num = 1; num <= N; num++) {
			people.add(num);
		}
	}
}