글 읽기 - 12852 1로 만들기2 제가 생각한 식이 맞는지 알려주세요 ㅠ

jhhh2222 3년 전 0

일단 리스트 크기는 혹시 몰라 넉넉하게 해뒀습니다.

제가 생각한 풀이는

3의 배수일때는 무조건 3으로 나누거

2의 배수일때 -1을 했을때 3의 배수가 되면 -1

-1을 해도 3의 배수가 안되면 2로 나눔

이렇게 생각했습니다.

제가 생각한 식이 잘못된것인가요?

#include <stdio.h>

int	main(void)
{
	int num_list[23] = { 0 };  
	int n;
	scanf("%d", &n);
	int count = 0;
	for(int i=0; i<23; i++)
	{

		num_list[i] = n; // 출력 두번째 줄을 위해 과정을 저장
		if (n == 1) // 1이 됐을시 멈춤, 연산횟수(count)에 i저장
		{
			count = i;
			break;
		}

		if (n % 3 == 0)             //3의 배수일시 3으로 나눔
			n /= 3;                      //3의 배수가 아닌 짝수일 경우 -1을 했을때 3의 배수이면 -1 아니면 나누기 2
		else if ((n + 2) % 3 == 0)
			n -= 1;

		else
			n /= 2;
	}
	printf("%d\n", count);
	for (int i = 0; i < 23; i++)
	{
		if (num_list[i] != 0)
		{
			printf("%d", num_list[i]); // 과정들 나열
		}
		if (num_list[i] > 1)  //마지막은 공백 x
		{
			printf(" ");
		}
	}
}

harinboy 3년 전 1

생각하신 알고리즘은 2049에 대해서 13이라는 틀린 답을 냅니다.

2049->2048->계속 2로 나누기를 하면 12번만에 1이 될 수 있습니다.

이 문제는 어떤 규칙을 세워서 푸는 것을 의도하지 않은 것으로 압니다.

전혀 모르겠다면 다이나믹 프로그래밍에 대해서 생각해보세요.

그리고 그냥 팁인데 백준 채점 시스템에서 프로그램이 출력할 때 마지막의 공백/줄바꿈은 무시합니다.

즉, 34~37번째 줄 없이 printf("%d ", num_list[i]); 해도 된다는 뜻입니다.

jhhh2222 3년 전 0

아 그렇군요 !

마지막 팁도 너무 도움되네요 감사합니다!!

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

문제

문제

출처

ICPC

12852 1로 만들기2 제가 생각한 식이 맞는지 알려주세요 ㅠ

jhhh2222 3년 전 0

harinboy 3년 전 1

jhhh2222 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말