글 읽기 - [c++] 1463번 틀린 이유를 모르겠습니다.

damek113 3년 전 0

문제의 예시대로 10을 입력하면 정상적으로 출력이 되지만

16을 입력할 경우 16 15 5 4 3 1로 5개가 나옵니다.

어느 부분이 문제인지 알려주시면 감사하겠습니다.

#include<iostream>
using namespace std;

int count(int num, int cnt) {
	if (num == 1) {
		cout << num << '\n';
		cout << cnt;
		return cnt;
	}
	if (num % 3 == 0) {
		
		if ((num - 1) % 2 == 0) {
			cnt++;
			return count(num /3, cnt); 
		}
		else if (num % 6 == 0 && (num - 1) % 2 != 0) {
			cnt++;
			return count(num / 3, cnt);//num이 6의 배수인 경우
		}
		else{
			cnt++;
			return count(num  - 1 , cnt);
		}
	
	}
	if (num % 2 == 0) {
		if ((num - 1) % 3 == 0 ) {
			cnt++;
			return count(num - 1, cnt);
		}
		else {
			cnt++;
			return count(num / 2,cnt);
		}
	}
	if (num % 2 != 0 && num % 3 != 0) {
		cnt++;
		return count(num - 1, cnt);
	}// 2의 배수도 3의 배수도 아닌 경우
}

int main() {
	int n;
	int c = 0;
	cin >> n;
	count(n, c);

}

khj878 3년 전 1

소스코드에서 아래부분 실행시 26,27번 줄에 의해 재귀함수가 if (num % 2 == 0)에서 if ((num - 1) % 3 == 0 )애 의해 3으로 나누어떨어질 경우로 가는것 같습니다.

해당 문제는 DP(동적프로그래밍)로 풀이가 가능한데 재귀함수보단 DP알고리즘을 공부하셔서 풀이해보시는 것도 좋은 방법인것 같습니다.

if (num % 2 == 0) {
		if ((num - 1) % 3 == 0 ) {
			cnt++;
			return count(num - 1, cnt);
		}
		else {
			cnt++;
			return count(num / 2,cnt);
		}
	}

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

문제

문제

출처

ICPC

[c++] 1463번 틀린 이유를 모르겠습니다.

damek113 3년 전 0

khj878 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말