나 잡아봐라 (라인> Dynamic_programming)

문제 링크

문제설명

연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건

1. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
2. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
3. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
4. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.

입력 형식

표준 입력의 첫 줄에 코니의 위치 C와 브라운의 위치 B를 공백으로 구분하여 순서대로 읽는다.

출력 형식

브라운이 코니를 잡을 수 있는 최소시간 N초를 표준 출력한다. 단 브라운이 코니를 잡지 못한 경우에는 -1을 출력한다.

예제

입력: 11 2

출력: 5

코니의 위치: 11 → 12 → 14 → 17 → 21 → 26

브라운의 위치: 2 → 3 → 6 → 12 → 13 → 26

브라운은 코니를 5초 만에 잡을 수 있다.

풀이

package Dynamic_programming;

import java.util.*;

public class line_나잡아봐라 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int co = sc.nextInt();
		int br = sc.nextInt();
		
		int pos[] = new int[200001]; //값을 min 초 취급
		int answer = -1;
		
		Queue<Integer> qu = new LinkedList<>();
		
		qu.add(br);
		
		while(true) {
			int num = qu.poll();
			
			int time = pos[num];
			int cony = 0;
			for(int i=1; i<=time; i++)
				cony += i;
			
			if(num == co + cony) {
				answer = pos[num];
				break;
			}
			
			int next=0;
			for(int i=0; i<3; i++) {
				if(i==0)
					next = num-1;
				if(i==1)
					next = num+1;
				if(i==2)
					next = num*2;
				
				if(next>=0 && next<200001 && pos[next] ==0) {
					qu.add(next);
					pos[next] = pos[num]+1;
				}
			}
		}
		
		System.out.println("answer " + answer);
	}
}

후기 (1h)

테스트 케이스가 하나라서 다른 반례가 있는지는 모르겠으나…

일단 5가 나오긴 함.

저번에 풀 때는 왜 버벅 거렸는지….

1. 일단 숨바꼭질과 유사했으나,, 왜 잊은건지 어쨌든
2. 브라운은 이십만이상의 위치로 가지 못하기때문에, pos[20만] 으로 설정
3. 또한 코니의 위치는 미리 구해놓지말고, pos[브라운 위치] 에 들어있는 값이 브라운이 그 위치에서 가질 수 있는 가장 작은 초이기때문에
4. 조건을 비교해줄 때, 코니의 위치는
   1. num = 브라운의 위치
   2. time = pos[num] = 브라운의 위치에서 가지는 시간
   3. cony = 코니의 시간은 (1+2+3+….+time)에 자신의 시간 더한 값이고
   4. if(num == cony + co) 브라운의 위치와 코니의 위치가 같다면
   5. 답은 브라운의 위치가 가지는 시간(최소 시간)이다!