백준 12934번 턴 게임

문제 링크입니다: https://www.acmicpc.net/problem/12934

그리디하게 접근해야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. x와 y의 합이 1 ~ K까지의 합이라면 가능한 경우이고 1 ~ K까지의 합이 아니라면 가능하지 않은 경우이니 -1을 출력해줍니다.

2. 핵심은 K ~ 1까지 순회하면서 그리디하게 큰 수부터 빼주는 것입니다.

-> 큰 수부터 빼준다면 덧셈의 횟수가 최소가 된다는 것은 자명합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        long long x, y;

        cin >> x >> y;

 

        if (!x && !y)

                 cout << 0 << "\n";

        else

        {

                 long long k = 1;

                 bool possible = true;

                 //1 ~ K의 합

                 while (1)

                 {

                         //가능한 경우

                         if (x + y == (k * (k + 1) / 2))

                                 break;

                         //가능하지 않은 경우

                         if (x + y < (k * (k + 1) / 2))

                         {

                                 possible = false;

                                 break;

                         }

                         k++;

                 }

                

                 if (!possible)

                         cout << -1 << "\n";

                 else

                 {

                         long long result = 0;

                         //제일 큰 수부터 뺀다

                         for (long long i = k; i >= 1; i--)

                         {

                                 if (x == 0)

                                          break;

 

                                 x -= min(x, i);

                                 result++;

                         }

                         cout << result << "\n";

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~