글 읽기 - 답은 맞췄는데 범위 설정 질문입니다..

le_effort 4년 전 0

첫번째가 실패코드

두번째가 성공코드인데요

둘의 차이점은

두번째 코드는 두 위치중 큰 값을 구해서

배열을 큰값을 기준으로

ex) 위치가 5 와 17 일 경우

0~17 까지 범위 지정

하고 목적지 값 출력

첫번째 코드는 코드 내에서 허용 할 수 있는 최대범위 100,000 까지 설정해서

목적지 값 출력 인데

왜 첫번째는 틀리게 나오나요?

visited 함수로 한번 방문 한 값은 두번 다시 방문 못하니까

첫번째 코드대로 위치의 최대값을 기준으로 배열 생성해서 하면 안되는 건가요...?

import java.io.*;
import java.util.*;
public class Main  {
	static boolean visited[];
	static int dp[];
	static int n;
	static int m;
	static int dx[]= {-1,1,2};
	static int max;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] t = br.readLine().split(" ");
		n= Integer.parseInt(t[0]);
		m = Integer.parseInt(t[1]);
		
	
		visited = new boolean[100001];
		dp = new int[100001];
	
		bfs();
		System.out.println(dp[m]);
	
	}
	public static void bfs() {
		visited[n]= true;
		Queue<Integer>q = new LinkedList<>();
		q.add(n);
		
		while(!q.isEmpty()) {
			int x = q.poll();
			for(int i=0; i<3; i++) {
				int poll_x;
				if(i==2) {
					poll_x = x*dx[i];
				}
				else {
					poll_x = x+dx[i];
				}
				if(poll_x >=0 && poll_x<=100000) {
					if(!visited[poll_x]) {
					dp[poll_x] = dp[x]+1;
					q.add(poll_x);
					visited[poll_x] = true;
					}
				}
			}
		}
	}
}

//------------------------------------------------------------------//



import java.io.*;
import java.util.*;
public class Main  {
	static boolean visited[];
	static int dp[];
	static int n;
	static int m;
	static int dx[]= {1,-1,2};
	static int max;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] t = br.readLine().split(" ");
		n= Integer.parseInt(t[0]);
		m = Integer.parseInt(t[1]);
		
		 max = 0;
		max = Math.max(m, n);
	
		visited = new boolean[max+1];
		dp = new int[max+1];
	
		bfs();
		System.out.println(dp[m]);
		
	}
	public static void bfs() {
		visited[n]= true;
		Queue<Integer>q = new LinkedList<>();
		q.add(n);
		
		while(!q.isEmpty()) {
			int x = q.poll();
			for(int i=0; i<3; i++) {
				int poll_x;
				if(i==2) {
					poll_x = x*dx[i];
				}
				else {
					poll_x = x+dx[i];
				}
				if(poll_x >=0 && poll_x<=max) {
					if(!visited[poll_x]) {
					dp[poll_x] = dp[x]+1;
					q.add(poll_x);
					visited[poll_x] = true;
					}
				}
			}
		}
	}
}

luniro 4년 전 1

N > K 라면 상관없지만 N < K 인 경우 범위를 K 값으로 제한하면 다음과 같은 반례가 존재합니다

입력: 1 15
정답: 5
(1-2-4-8-16-15)
출력: 6
(1-2-3-6-7-14-15)?

le_effort 4년 전 0

그럼 순간이동 *2 하는 걸 고려해서

max 에다가 +2 정도만 해줘도 문제가 해결 되나요??

djm03178 4년 전 1

*2 후 두 번 이상 -1을 하는 경우 *2를 하기 전에 먼저 -1을 하는 게 이득이기 때문에 그렇게 해도 최적해를 구할 수 있습니다.

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

문제

문제

출처

ICPC

답은 맞췄는데 범위 설정 질문입니다..

le_effort 4년 전 0

luniro 4년 전 1

le_effort 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말