문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258707
이 문제를 풀기 위해서, 매 라운드 마다 일어 나는 일을 정리해 보겠습니다.
- 카드 뭉치에서 2장씩 뽑 습니다.
- 코인으로 카드를 1 또는 2장 교환할 수도 있고, 안할 수도 있습니다.
- 2장의 카드에 적힌 수의 합이 n+1 이 되도록 카드 두장을 냅니다.
1번, 2번을 모두 할수 있어야 다음 라운드로 진행합니다.
2번의 조건과 3번의 조건이 문제의 진행에 서로 영향을 준다고 생각하게 되면, 이문제를 매우 복잡하게 접근해서, 문제를 풀 수 없는 경우가 많을 것 같습니다.
이 문제를 단순하게 만들어주는 아래 조건을 잘 활용해야 합니다.
cards의 원소는 중복되지 않습니다.
그러면 위의 조건을 고려해서, n+1 이 되는 2개의 카드를 선택하는 방법을 알아 보겠습니다.
a 카드 + b 카드 = n + 1 입니다.
따라서, n + 1 - a = b 카드에는 중복이 없기 때문에, b 카드를 가지고 있지 않다면, a 카드를 낼 수 있는 경우는 없습니다.
따라서, 루프 1개로, a, b 카드를 고를 수 있습니다.
for card1 in my_cards:
if N + 1 - card1 in my_cards:
이제 가장 고민되는 부분인 코인으로 카드를 받아야 하나? 말아야 하나? 이 부분을 알아보겠습니다.
매 라운드 마다, 카드를 안받는 경우, 첫번째 카드를 받는 경우, 두번째 카드를 받는 경우, 카드를 2개 받는 경우 이렇게 4개의 분기를 만들게 되면, 대충 계산해도 아래와 같이 엄청 나게 큰 숫자가 나오게 됩니다. 카드의 최대 숫자가 1000임으로 모든 경우의 수는 대략 아래와 같습니다.
$$ 4^{(1000/2)} = 4^{500} $$
4의 5제곱이 1024 인대, 4의 500 제곱이면, 21억이나 10억 보다 매우 큰 숫자 입니다.
즉, 이문제를 시간안에 풀기 위해서는, 카드를 받는 경우의 수를 분기하지 않고, 문제를 풀어야 합니다.
분기를 하지 않으려면, 아래 4가지 경우를 한번에 처리할 수 있는 방법을 고민해 봐야 합니다.
- 카드를 안받는 경우
- 첫번째 카드를 받는 경우
- 두번째 카드를 받는 경우
- 카드를 2개 받는 경우
카드를 받는다 안 받는다 이거를 꼭 매 라운드에 결정을 해야 되는가? 라는 의문가질 수 있습니다.
카드를 매라운드에서 버리지 않고, 어딘가에 모아 둔다면 나중에 카드가 필요할 때, 이전 라운드에서 카드를 뽑은 것으로 치고, 카드가 필요한 라운드에 가서, 모아둔 곳에서 카드를 받아 올 때, 코인을 소모하는 것입니다.
이렇게 하면 문제의 규칙을 어기지 않고, 규칙을 약간 변형해서 아래와 같이 문제를 푸는 것이 가능합니다.
- 카드 뭉치에서 항상 2장을 뽑아서, available_cards 에 넣어 둡니다.
- 2장의 카드에 적힌 수의 합이 n+1 이 되도록 카드 두장을 냅니다.
- 카드 두장을 낼 수 없는 상황이 생기면
- 코인이 1이상인 경우에, 내가 가지고 있는 카드에서 1장을 선택하고, available_cards 카드에서 1장을 선택하여 n+1이 되는 카드 2장을 냅니다. 코인이 1개 감소합니다.
- 코인이 2개 이상인 경우에, available_cards 에서 n+1이 되는 카드 2장을 선택합니다. 코인이 2개 감소합니다.
위와 같이 문제를 접근하면, 1000/2 횟수 안에 문제를 풀 수 있습니다.
$$ 1000 / 2 = 500 $$
코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul
댓글 없음:
댓글 쓰기