글 읽기 - 1을 가장 먼저 빼는 이유?

rds257 2년 전 0

안녕하세요

문제 풀이 중 1을 가장 먼저 빼야 하는 이유가 궁금합니다.

아래와 같은 코드는 잘못된 코드입니다.

하지만 틀린 이유를 잘 모르겠습니다.

해답을 알려주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		for (int i = 2; i < dp.length; i++) {
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1;
			}
			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
			}
			if (i % 3 != 0 && i % 2 != 0) {
				dp[i] = dp[i - 1] + 1;
			}
		}
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println("dp[" + i + "] +  : " + dp[i]);
//		}
		System.out.println(dp[n]);
	}
}

kipa00 2년 전 1

반례입니다.

6

rds257 2년 전 0

답변 주셔서 감사합니다.

2와 3의 공배수인 30에서 4가 답이지만 5가 나왔었네요.

따라서 최소공배수인 6에 대한 처리가 필요했습니다.

덕분에 고민이 해결되었습니다.kipa00님께 다시 한번 감사드립니다.

easy16 2년 전 0

올려주신 코드로 테스트하면서 찾은 내용 공유할게요

dp[30]=5 나오는 이유가

11라인에서 dp[30]=4 를 넣었지만, 14라인에서 dp[15]=4랑 dp[29]=5를 비교한 값을 다시 dy[30]에 쓰기 때문에 이전에 계산한 4가 없어지기 때문이네요.

그러므로 루프 첫줄에서 dp[i] = dp[i-1] + 1;로 이전에 구해놓은 값을 먼저 저장해 놓고 비교를 해야 해결이 되네요.

dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1; =>dp[i] = Math.min(dp[i], dp[i / 3]+1);

덕분에 잘 배우고 갑니다. 수고하세요.

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

문제

문제

출처

ICPC

1을 가장 먼저 빼는 이유?

rds257 2년 전 0

kipa00 2년 전 1

rds257 2년 전 0

easy16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말