글 읽기 - 정말 완벽한데 머가 틀린지 모르겠어요 ㅠㅠ

forybm 8년 전 1

어떤 예제를 대입해봐도 다 답이 나오는데 말이죠 ㅠㅠ

#include <stdio.h>

int main(){
	
	int n,t=0;
	
	scanf("%d",&n);
	

	while(1){
	
		while(n%3==0){
		n=n/3;
		t++;
	}
		
		while(n%2==0){
		n=n/2;
		t++;
	}
	if(n==1) break;
	n=n-1;
	t++;
	}
	
	
	 
	
	printf("%d\n",t);
	
	return 0;
}

yukariko 8년 전 1

정말 다 해보셨나요??

10을 넣어보니 4가 나옵니다.

10 -> 9 -> 3 -> 1로 3이 나와야합니다.

forybm 8년 전 0

정말 죄송하네요 .. ㅠㅠ 감사합니다 노력할께요

forybm 8년 전 0

생각보다 무지복잡하네요 ㅋㅋ

yukariko 8년 전 1

이 문제는 완전탐색+가지치기나 DP가 필요합니다.

DP에 대한 설명은

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95_-_dynamic_programming

를 참고해보세요.

forybm 8년 전 0

정말감사합니다.. 공부하고 답을한번 찾아내보겠습니다. 정말감사해요 !!

forybm 8년 전 0

후.. dp의 개념에대해 많이 공부해봤는데요 ㅠㅠ 이 문제에서는

dp문제를 어떻게 정의를 해야될가요..

힌트좀 주시면 안될까요?

저는 dp[n][1] 전 수에서 1을뺀것

dp[n][2] 전 수에서 2로 나눈것

dp[n][3] 전 수에서 3으로 나눈것 이렇게 잡았는데

솔직히 맞는지도 모르겠고 감이 없네요 ㅠㅠ

yukariko 8년 전 0

dp[n] = n으로 1을 만드는 최소횟수로 생각하면 dp[n+1] 이 어떻게 정의될 지 알 수 있을겁니다.

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

문제

문제

출처

ICPC

정말 완벽한데 머가 틀린지 모르겠어요 ㅠㅠ

forybm 8년 전 1

yukariko 8년 전 1

forybm 8년 전 0

forybm 8년 전 0

yukariko 8년 전 1

forybm 8년 전 0

forybm 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말