2847 게임을 만든 동준이 [미완]

동준아아아아아악 뭐가 문제니

 

 

일단 입력값이 100이라 제곱번 확인해도 될 것 같았다.

 

어떻게 풀지 이리저리 생각해보니 한번 쭉 확인하면서 값이 감소하면서 최소인 값을 찾는다

 

그위의 예시를 보면 80과 5가 작아지는 값에 해당되는데 그 중 최솟값인 5를 잡음

 

그 다음 5 이전의 값을 5 4 3 2 1로 만들어준다. 조건에 만족하면서 차가 최소가 하게 하려면 이렇게 돼야 할 것 같았음 

 

시도 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

using namespace std;

int n;
int v[105];
int sum;

void check()
{
    int min_idx = 0;

    for (int i = 2; i <= n; i++)
    {
        if (v[i - 1] > v[i] && v[min_idx] > v[i])
        {
            min_idx = i;
        }
    }

    if (min_idx == 0)
        return;
    else
    {
        int value = v[min_idx] - 1;
        for (int i = min_idx - 1; i > 0; i--)
        {
            sum += v[i] - value;
            v[i] = value;
            value--;
        }
    }

    check();
}

int     main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);

    v[0] = 20005;
    check();
    
    cout << sum << endl;

    return 0;
}

 

왜 틀렸는지 고민해보니 n = 1인 값을 처리 안 해줬다!

 

아래에 고쳐서 제출했음

 

시도 2

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

using namespace std;

int n;
int v[105];
int sum;

void check()
{
    int min_idx = 0;

    for (int i = 2; i <= n; i++)
    {
        if (v[i - 1] > v[i] && v[min_idx] > v[i])
        {
            min_idx = i;
        }
    }

    if (min_idx == 0)
        return;
    else
    {
        int value = v[min_idx] - 1;
        for (int i = min_idx - 1; i > 0; i--)
        {
            sum += v[i] - value;
            v[i] = value;
            value--;
        }
    }

    check();
}

int     main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);

    if (n == 1)
    {
        printf("%d\n", v[1]);
        return 0;
    }

    v[0] = 20005;
    check();
    
    cout << sum << endl;

    return 0;
}

 

v[1]이 문제였다.. 

 

다음으로 생각해보니 5를 확인한 다음 수정하고 다음으로 80을 수정하는데 80부터 5까지 수정해야 했다. 

 

이전 코드가 무조건 0까지 수정해버려서 문제였으니 이제는 수정한 인덱스까지 수정하게 바꿔주면 될 것 같았다. 

 

시도 3

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

using namespace std;

int n;
int v[105];
int sum;

void check(int start)
{
    int min_idx = 0;

    for (int i = 2; i <= n; i++)
    {
        if (v[i - 1] > v[i] && v[min_idx] > v[i])
        {
            min_idx = i;
        }
    }

    if (min_idx == 0)
        return;
    else
    {
        int value = v[min_idx] - 1;
        for (int i = min_idx - 1; i > start; i--)
        {
            sum += v[i] - value;
            v[i] = value;
            value--;
        }
    }

    check(min_idx);
}

int     main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);

    if (n == 1)
    {
        printf("%d\n", v[1]);
        return 0;
    }

    v[0] = 20005;
    check(0);
    
    cout << sum << endl;

    return 0;
}

그래도 틀렸다...

 

생각해보니 점수가 높아지면 문제니깐 1 2 3 4 5로 수정하는게 아니라 5 5 5 5 5로 수정해도 되는 것 같다. 

 

아 그런데 그렇게 하면 예시가 안 돌아가구나 5 5 5 5 5 아닌가보다.

 

으음... 동준아 다음에 보자