글 읽기 - 반례가 궁금합니다.

lys9546 3년 전 0

새로운 배열을 만들어 역추적을 실행 했으나 문제점을 잘 모르겠습니다.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;


int dp[1000002];
int go[1000002];

int main()
{
	int num;

	cin >> num;
	dp[0] = 987654321;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;

	for (int i = 4; i < 1000002; i++)
	{
		dp[i] = 987654321;

        int a = dp[i / 2] + 1;
        int b = dp[i / 3] + 1;
        int c = dp[(i-1) / 2] + 2;
        int d = dp[(i - 1) / 3] + 2;
        int e = dp[i - 1] + 1;
		if (i % 2 == 0)
		{
			dp[i] = min(dp[i],a);
		}
		if (i % 3 == 0)
		{
			dp[i] = min(dp[i],b);
		}
		if ((i - 1) % 2 == 0)
		{
			dp[i] = min(dp[i], c);
		}
		if ((i - 1) % 3 == 0)
		{
			dp[i] = min(dp[i], d);
		}
		dp[i] = min(dp[i], e);

        if(dp[i] == a)
        {
         go[i] = i/2;
        }
        else if(dp[i] == b)
        {
          go[i] = i/3;
        }
        else if(dp[i] == c)
        {
          go[i] = i-1;
        }
        else if(dp[i] == d)
        {
          go[i] = i-1;
        }
        else if(dp[i] == e)
        {
          go[i] = (i-1);
        }
	}
	
	cout << dp[num]<<"\n";

  int tmp = num;
  while(tmp>=1)
  {
    cout<<tmp<<" ";
    tmp = go[tmp];
  }
  if(num!=1)
    cout<<1;


    return 0;
}

ghghgh777 3년 전 0

Input : 33

Your answer :

33 16 8 4 2 1

lys9546 3년 전 0

제가 그냥 잘못생각했네요

감사합니다.

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

문제

문제

출처

ICPC

반례가 궁금합니다.

lys9546 3년 전 0

ghghgh777 3년 전 0

lys9546 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말