[프로그래머스/C++] n + 1 카드게임 (2024 KAKAO WINTER INTERNSHIP)

 

 

문제

문제 설명

 

  

 

풀이

 

[문제 풀이]

 

이 문제는 카드를 구매해 원하는 숫자를 만들면서, 최대한 라운드를 길게 가기 위해서 언제 카드를 사야 하는지 묻는 문제다.

처음에는 특정 라운드에 나온 카드를 살지 말지 어떻게 판단할까 고민했는데, 카드의 길이를 보니 1000밖에 되지 않았다.

그래서 최대 1000*1000번 비교하면 해결할 수 있기 때문에 단순한 for문의 반복으로 해결했다.

 

먼저 당연한 말이지만 내가 동전을 사용하지 않고 가지고 있는 카드를 사용하는게 coin의 소모를 최대한 적게 하면서 round를 길게 가는 방법이다. 그래서 동전을 1개만 사용해도 되는 경우와 2개 사용해야 하는 경우로 경우를 나눴다,

 

단순히 for문으로 해결할 수 있는 이유는 카드가 중복이 없으므로, 특정 숫자를 만들기 위해서는 하나의 숫자에는 하나의 짝만 있기 때문이다.

 

그래서 특정 라운드에서 구매할수 있는 카드를 for문을 돌려 이전에 나와있는 카드와 더해 내가 원하는 target숫자를 만들 수 있는지 비교한다.

이 과정을 요약하면 아래와 같이 나타낼 수 있다.

 

1. 만약 내가 처음에 가지고 있던 카드와 더해서 target 숫자가 되면 coin을 하나 사용해 카드를 구매하고, target숫자를 만들 수 있는 Case에 +1을 더한다.
2. 만약 내가 처음에 가지고 있던 카드가 아닌 숫자와 더해서 target 숫자가 되면 specialCase로 구분해 구매하지 않고, 분류만 해둔다.
3. 만약 현재 라운드에 더 이상 제출할 수 있는 Case가 없으면 specialCase가 0보다 큰지 확인하고 0보다 크다면 coin을 2개 소모해 다음 라운드로 넘어간다.
4. 위 과정을 반복한다.

​

[아이디어 정리]

1. 카드의 숫자가 중복되지 않으므로 하나의 숫자에는 짝이 하나만 존재한다. (이중 for문으로 해결 가능)
2. 처음에 가지고 있는 카드를 최대한 사용하는 게 최대 라운드로 가는 방법이므로, coin을 최대한 적게 사용한다.
3. coin을 2개 사용해야하는 specialCase와 coin을 하나만 사용해도 되는 일반 Case로 구분하고, 만약 일반 Case라면 coin을 사용해 현재 내가 더해서 낼 수 있는 card 조합의 수를 +1한다.
4. 만약 현재 라운드에서 내가 더해서 낼 수 있는 card 조합의 수가 0이라면, specialCase를 확인해 숫자가 0보다 큰지 확인한다. 만약 specialCase가 1보다 크다면 coin을 두개 소모해 다음 라운드로 갈 수 있으므로, coin을 2개 소모해 카드를 내고 다음 라운드로 간다.
5. 위 과정을 더 이상 다음 라운드로 못 갈때까지 반복한다.

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int solution(int coin, vector<int> cards) {
    // 대충 1000^2 안에 해결
    int targetNum=cards.size()+1, firstCardNum=cards.size()/3, round=1, combiNum=0, specialCase=0;
    for (int i=0; i<firstCardNum-1; i++)
    {
        for (int j=i+1; j<firstCardNum; j++)
        {
            if (cards[i]+cards[j]==targetNum)
            {
                combiNum+=1;
                break;
            }
        }
    }
    for (int i=firstCardNum; i<cards.size(); i+=2)
    {
        for (int j=0; j<i; j++)
        {
            if (j<firstCardNum)
            {
                if (cards[i]+cards[j]==targetNum&&coin>=1)
                {
                    combiNum+=1;
                    coin-=1;
                }
                if (cards[i+1]+cards[j]==targetNum&&coin>=1)
                {
                    combiNum+=1;
                    coin-=1;
                }
            }
            else // 코인을 두개 사용해야하는 경우
            {
                if (cards[i]+cards[j]==targetNum)
                {
                    specialCase+=1;
                }
                if (cards[i+1]+cards[j]==targetNum)
                {
                    specialCase+=1;
                }
            }            
        }
        // 예외처리
        if (cards[i]+cards[i+1]==targetNum)
        {
            specialCase+=1;
        }
        if (combiNum>0)
        {
            round+=1;
            combiNum-=1;
        }
        else{
            if (specialCase>0&&coin>=2)
            {
                specialCase-=1;
                round+=1;
                coin-=2;
            }
            else
            {
                break;
            }
        }
    }
    return round;
}

 

---

 

처음에 for문을 반복하다가 coin을 두개 사용해야하는 경우였는데 1개 사용하는 경우로 착각했다.

for문의 반복이 너무 많아보이면 Set을 사용해 빠르게 찾고 계산하는 방법도 있겠지만, 숫자가 1000까지밖에 없어서 그냥 해결했다...

 

프로그래머스