글 읽기 - java stackoverflow 에러 도와주세요!!

haeran97 5년 전 0

100%까지 채점하다가 '틀렸습니다' 뜨길래

숫자 큰거 넣으니까 스택오버플로 에러가 나네요. 검색해보니까 재귀가 너무 반복되면 메모리 부족으로 뜬다는데

제 방법 자체가 틀린 걸까요? 고수님들 도와주세요ㅠ.ㅜ~~

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int dp[] = new int[1000001];
		
		dp[1] = 1; dp[2] = 1; dp[3] = 1;
		
		if(dp[n]==0) System.out.println(Find1Cost(dp,n));
		else System.out.println(dp[n]);
		
	}
	
	
	public static int Find1Cost(int[] dp, int n) { //dp[n]을 구하는 함수: n을 1로 만드는 최소연산횟수
		int div3=0;
		int div2=0;
		int minus=0;
		int max = 99999999;
		
		if (n%3!=0) div3=max; 
		else if (dp[n/3]==0) div3 = Find1Cost(dp,n/3); //업으면 찾음
		else div3=dp[n/3];//있으면 있는거 쓰음
		
		if (n%2!=0) div2=max;
		else if (dp[n/2]==0) div2 = Find1Cost(dp,n/2);
		else div2=dp[n/2];
		
		if(dp[n-1]!=0) minus = dp[n-1];
		else minus = Find1Cost(dp,n-1); //없으면 찾아야 하쥬
		
		dp[n] = Math.min(div3, Math.min(div2, minus)) + 1;
		
		return dp[n];
	}
}

djm03178 5년 전 1

틀렸습니다는 에러와는 연관이 전혀 없습니다. 출력한 답이 틀렸으니까 틀린 것입니다.

입력이 1일 때 정답은 1이 아니라 0입니다.

haeran97 5년 전 0

아 그랬군요 또 하나 알아갑니다...

애초에 dp[1]=1 로 한게 문제였네요.. 정말 감사합니다 !!! 고쳤더니 바로 맞았어요

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

문제

문제

출처

ICPC

java stackoverflow 에러 도와주세요!!

haeran97 5년 전 0

djm03178 5년 전 1

haeran97 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말