[백준] S1 3258 컴포트 (java)

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

3258번: 컴포트

 

풀이

 

1) 방문체크 및 장애물을 나타내는 boolean형 배열 obstacle을 생성한다.

2) K = 1부터 1씩 증가 시키면서 Z 칸에 도달하는지 확인한다. N은 1000 이하이므로 999까지만 증가시키자.

2-0) 현재 칸이 Z 칸이면 K 출력.

2-1) 방문되지 않은 칸 and 장애물이 없는 칸 일 경우 해당 칸을 방문체크 해준다.

2-2) 방문된 칸 or 장애물이 있는 칸일 경우 해당 K 만큼 증가해서 Z 칸으로 갈 수 없다는 뜻이다.

3) 2) 반복하면서 최소 K를 찾는다.

4) 만약 K=999 까지 답이 안나오면 답이 없다는 의미이다. -1 출력.

 

주의사항

 

1) 범위를 넘으면 N 만큼 빼줘야한다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class BJ_S1_3258_컴포트 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,Z,M,board[];
	static boolean obstacle[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		Z = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		obstacle = new boolean[N+1];
		tokens = new StringTokenizer(input.readLine());
		for(int m=0; m<M; m++) {
			obstacle[Integer.parseInt(tokens.nextToken())] = true;
		}
		System.out.println(solve());
	}

	private static int solve() {
		outer : for(int i=1; i<1000; i++) {
			int cur = 1;
			boolean isVisited[] = obstacle.clone();
			while(cur<1000) {
				if(cur == Z) {
					return i;
				}
				if(!isVisited[cur]) {
					isVisited[cur] = true;
				}else {
					break;
				}
				cur += i;
				if(cur>N) {
					cur = cur-N;
				}
			}
		}
		return -1;
	}

	static String src =

			"7 6 2\r\n" + 
			"2 4";
}

 

후기

 

 실버문제는 이제 쉬운것 같다. 문제이름은 왜 컴포트일까?