글 읽기 - 1463번 1로 만들기 문제 질문입니다.

boffin 6년 전 0

틀렸습니다

라고 결과가 나오는데

왜 그러는지 모르겠습니다..

도와주세요ㅠ

#include<stdio.h>

int main() {
	int N;
	int count = 0;
	scanf("%d", &N);

	for (; N != 1;) {
		if (N % 3 == 0) N = N / 3;
		else if ((N - 1) % 3 == 0)N -= 1;
		else if (N % 2 == 0) N = N / 2;
		else N -= 1;

		count++;
	}
	printf("%d\n", count);
}

kyhdudgns113 6년 전 1

n = 1024 일때, 답은 10인데 이 코드로는 13이 나오네요.

만약, n 이 3의 배수로 나눠지지만, 숫자를 조금만 더 빼면 2의 지수승으로 나온다고 가정하면, n 에 3을 나누는것이 아닌, 1을 빼는것이 더 많이 줄어들 수 있습니다.

그렇다고 1을 빼는 조건문을 맨 위에 두자니, n이 3의 지수승이라면, 1을 빼는것보다 3을 나누는것만 반복하는것이 훨씬 적게 걸리겠죠.

따라서 이는 산술연산으로는 해결하기가 매우 힘들어보입니다.

simm4256 6년 전 1

16->8->4->2->1 :: 4

16->15->5->4->3->1 :: 5

DP에 대해 알아보세요

boffin 6년 전 0

kyhdudgns113님 simm4256님 감사합니다!!!!!!

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

문제

문제

출처

ICPC

1463번 1로 만들기 문제 질문입니다.

boffin 6년 전 0

kyhdudgns113 6년 전 1

simm4256 6년 전 1

boffin 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말