글 읽기 - 해당 문제를 출제한 의도 파악을 잘 못하겠습니다..

kwak2418 2년 전 1

점화식을 구하긴 했는데 틀렷네요...

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define MAX 1001
#define endl "\n"
#define tab " "
#define MOD 1000000009
#define INF 987654321
typedef pair<int, int> pai;
typedef vector<int>::iterator iter;
typedef unsigned long long ull;

int max(const int &a, const int &b)
{
    return a > b ? a : b;
}

int min(const int &a, const int &b)
{
    return a < b ? a : b;
}

bool comp(const int &a, const int &b)
{
    return a > b;
}

int n;
ull dp[MAX];

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    dp[2] = 2;
    dp[3] = 3 ; // +1 복사 +1 붙여넣기 +1 붙여넣기
    // dp[4] = dp[2] +1 +1 // 복사 붙여 넣기=4 
    // dp[5] =  dp[2] +1 +1 +1 ;// 1 ->복사 -> 붙여 넣기 4번 =5 
    // dp[6] =  dp[3] +1 +1 // 3 +1 복사 +1 붙여 넣기  =5
    // dp[7] = dp[4]+1+1+1 // 7
    // dp[8] = dp[4] +1 +1 // 6
    // dp[9] = dp[3] +1 +1 +1 // 6 -> 복사 붙여넣기 3번
    // dp[10] = dp[5] +1 +1 //7
    // dp[11] = dp[12] +1
    // dp[12] = dp[6]  +1 +1  // 7
    // dp[13] = dp[7] +1 +1 +1
    // dp[14] = dp[7] +1 +1 
    // dp[17]= dp[18] +1
    // dp[18] = dp[6] +1 +1 +1  // 8  - > dp[9]  +1 +1
    
    for (int i = 4; i <=n; i++)
    {
        int k=0;
        if(i%3==0) //먼저 3으로 나눠 지면 3으로 해당 되는 계산
        {
            // dp[18]= dp[6] +3
            k=i/3; // 
            dp[i]=dp[k]+3; // 
            continue;
        }
        else if(i%2==0)
        {
            // dp[8]= dp[4] +2
            k=i/2;
            dp[i]=dp[k]+2;
            continue;
        }
        else //  둘다 해당 안되면 소수 
        {
            //dp[11]= dp[12] +1(12만든 후 하나 제거), dp[12]=dp[6]+2   --> dp[11]=dp[6]+2+1 -> dp[11]=dp[6]+3
            dp[i]=dp[(i+1)/2] +3;
        }
    }
    cout << dp[n];
    
  
}

djm03178 2년 전 0

이 문제가 특정 점화식으로 풀리는 문제인지는 모르겠습니다. 하지만 지금처럼 간단한 형태는 아닐 거라고 생각합니다. 이 문제는 BFS로 푸는 문제입니다.

kwak2418 2년 전 0

알려주신대로 BFS 공부해서 만들어 봤는데요 예제는 모두 통과인데 Out of Bound가 나오네요...

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define MAX 2001
#define endl "\n"
#define tab " "
#define MOD 1000000009
#define INF 987654321
typedef pair<int, int> pai;
typedef vector<int>::iterator iter;
typedef unsigned long long ull;

int max(const int &a, const int &b)
{
    return a > b ? a : b;
}

int min(const int &a, const int &b)
{
    return a < b ? a : b;
}

bool comp(const int &a, const int &b)
{
    return a > b;
}

int n;
typedef struct _CLIP
{
    int screen, clip, time; //화면,복사한 개수,시간
} Clip;
bool dp[MAX][MAX]; //dp[i][x] = 현재 화면에 i개 , 클립보드에 x개 복사 상태

int BFS()
{
    queue<Clip> q;
    Clip init_c = {1, 0, 0};
    q.push(init_c);
    dp[1][0] = true; //초기 화면에 한개 보이고 복사한 것 없음

    while (!q.empty())
    {
        Clip c;
        int screen = q.front().screen;
        int clip = q.front().clip;
        int time = q.front().time;
        q.pop();
        if (screen == n) // 현재 화면에 있는 개수와 원하는 개수가 같을 경우 리턴
        {
            return time;
        }
        if (screen > 0 && screen < MAX) //화면에 있는 그림을 클립보드에 복사 하거나(1번 조건),현재 상태에서 1개를 제거하기 위해서는(3번 조건)   screen에 1개 이상 있어야함
        {
            if (dp[screen][screen] == false) //해당 스크린에 있는 그림을 클립보드에 복사 하지 않은 상태라면
            {
                dp[screen][screen] = true;
                c.clip = screen;   //클립보드에 화면에 있는 것 복사
                c.time = time + 1; //시간증가
                c.screen=screen;
                q.push(c);
            }
            if (dp[screen - 1][clip] == false) //한 개 제거한 상태가 존재 하지 않았던 상태라면
            {
                dp[screen - 1][clip] = true;
                c.screen = screen - 1; //화면에서 하나 제거
                c.time = time + 1;     // 시간증가
                c.clip=clip;
                q.push(c);
            }
            //클립보드에 있는거 붙여 넣기 위해서는
        }
        if (clip > 0 && clip < MAX) // clip에 있는거 붙여넣기
        {
            if (dp[screen + clip][clip] == false)
            {
                dp[screen + clip][clip] = true;
                c.screen = screen + clip;
                c.time = time + 1;
                c.clip=clip;
                q.push(c);
            }
        }
    }
}

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    cout << BFS();
}

djm03178 2년 전 1

screen + clip이 MAX를 넘어갈 때에는 붙여넣기를 수행하지 않아야 합니다.

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

문제

문제

출처

ICPC

해당 문제를 출제한 의도 파악을 잘 못하겠습니다..

kwak2418 2년 전 1

djm03178 2년 전 0

kwak2418 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말