글 읽기 - 반례를 찾고싶습니다ㅠㅠ

wldnswldnswl 3년 전 0

문제에서 주어진 테스트케이스와

2 3

0 1

과 같이 visit배열을 처리해줘야 하는 테케까지는 만들어서 풀었는데,, (처음에 visit도 빼먹었더라구요....)

계속 틀렸습니다가 떠서 다른 테스트케이스를 찾아야할거같습니다..ㅠㅠ

제 코드에서 이상한 점이나 다른 반례를 말씀해주시면 감사하겠습니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
	static final int INF = 100000001; 
	static boolean[] visit = new boolean[2*INF]; // 치킨집이 지어젔는지 확인하는 배열
	static int k = 0; // k: 지을 집의 수
	static long ans = 0;
	public static void main(String[] args) throws IOException {// -- start of main--
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 첫째줄 입력
		int n = Integer.parseInt(st.nextToken()); // n(치킨 집의 수)입력
		k =  Integer.parseInt(st.nextToken()); // k(지을 집의 수)입력
		st = new StringTokenizer(br.readLine(), " "); // 첫째줄 입력
		Queue<int[]> q = new LinkedList<int[]>(); // 치킨집에서부터 좌우로 움직이기 위해 사용하는 큐.
		for (int i = 0; i < n; i++) { //n개의 치킨집을 입력
			int tmp = Integer.parseInt(st.nextToken())+INF; // 음수는 양수로, 양수는 2배 인덱스로.
			visit[tmp]=true;
			q.offer(new int[] {tmp, 0}); // 해당 위치 큐에 넣기
		}// --- end of input ---
		
		long distance =0; // 거리를 저장하는 변수
		while(!q.isEmpty()) { //큐가 빌때 까지
			if(k <= 0) break; // 집을 모두 지었으면 break;
			int[] ob = q.poll();//현재 위치 꺼내기
			int loc = ob[0];
			int nextD = ob[1] + 1;
			if(loc-1 >=0 && !visit[loc-1]) {//왼쪽에 집이 안지어져있으면
				visit[loc-1]=true;
				q.offer(new int[] {loc-1,nextD});// 왼쪽에 넣기.
				ans += (long)nextD;
				k--;// 집을 지었으므로 k--
			}// end of if (왼쪽으로 이동 성공)
			if(loc+1 < INF*2 && !visit[loc+1]) {// 오른쪽에 집이 안지어져있으면
				visit[loc+1]=true;
				q.offer(new int[] {loc+1,nextD});// 오른에 넣기.
				k--;// 집을 지었으므로 k--
				ans += (long)nextD;
			}// end of if (오른쪽으로 이동 성공)
		} // 집 짓기 성공
		System.out.println(ans); // 거리 출력
	} // --end of main--
}//-- end of class--

pichulia 3년 전 1

반례입니다.

1 1
0

pichulia 3년 전 1

그리고

https://www.acmicpc.net/board/view/56145

이 데이터도 틀릴겁니다.

wldnswldnswl 3년 전 0

덕분에 고쳤습니다!!

정말 감사합니다ㅠㅠㅠㅠ

부족한 부분을 더 알게됐네요,, 감사해요!!!!

혹시 다른 분들 보실까봐

고친부분 1) 오른쪽에 집 넣는 if문에서 k>0인 조건을 추가했습니다. 지어야 하는 집의 갯수가 1개인 경우 집을 지었다면 k가 0이 돼서 오른쪽 집을 짓는 코드를 실행하지 않고 종료 돼야 하는데, 제 코드에서는 k>0인조건을 넣지 않아 지어야 하는 집의 갯수가 1개인 경우에도 왼쪽, 오른쪽 모두 지어주게되었습니다.

고친부분 2) 거리가 long형이여야 최대크기의 인풋에서 오류가 안나는데..(이부분 정확힌 이해못했습니다ㅠㅠ) 큐 속 distance가 int형이라서 오류가 났습니다! long형으로 고쳐서 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾고싶습니다ㅠㅠ

wldnswldnswl 3년 전 0

pichulia 3년 전 1

pichulia 3년 전 1

wldnswldnswl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말