[프로그래머스] n + 1 카드게임

문제

프로그래머스

입력

coin:Int = 동전 개수
cards:[Int = 카드 뭉치

 

결과

answer: Int = 최대로 진행할 수 있는 라운드 수

해석

다음 라운드 수로 진행할 수 있는 경우의 수는 다음과 같다.

공통목표는 현재 들고 있는 카드 2개의 합이 n+1을 만족해야 넘어갈 수 있다

• 조건 A: 처음 갖고 있는 카드 2개로 조건 만족, coin 소모 x , 가장 좋은 방법
• 조건 B: 처음 갖고 있는 카드 1개 +  새로 뽑은 카드로 조건 만족, coin 소모 1개 
• 조건 C: 새로 뽑은 카드 2개로 조건 만족, coin 2소모

여기서 중요한 점은 새로 뽑는 카드들은 뒤에서 사용할 때 coin을 소모하는 개념으로 일단 담아놓는다.

담는 순간 바로 coin을 소모하면 또 다른 경우의 수를 계산할 수 없다.

 

코드

func solution(_ coin:Int, _ cards:[Int]) -> Int {
    var coin = coin
    let n = cards.count
    var point = n/3
    var myCards = Array(cards[0..<point]) // n/3개 가지고 시작
    var keepCards: [Int] = []
    var round = 1
    let target = n+1
    
outer:
    while true {
        // 코인도 없고 낼 수 있는 카드도 없으면
        if (myCards.isEmpty && coin <= 1) || (point == n) {
            break
        }
        // 미리 담아 놓는다. coin 소모는 나중에
        let card1 = cards[point]
        let card2 = cards[point+1]
        keepCards.append(card1)
        keepCards.append(card2)

        for i in 0..<myCards.count-1 {
            for j in i+1..<myCards.count {
                let myCard1 = myCards[i]
                let myCard2 = myCards[j]
                // 조건A: 내 카드에서 2장을 뽑을 수 있으면
                if (myCard1+myCard2) == target {
                    round += 1
                    point += 2
                    myCards.remove(at: i)
                    myCards.remove(at: i > j ? j : j-1)
                    continue outer
                }
            }
        }
       
        // 조건B: 코인이 1개 이상 남아있고 내카드+킵해둔 카드를 낼 수 있으면
        if coin >= 1 {
            for i in 0..<myCards.count {
                for j in 0..<keepCards.count {
                    let myCard = myCards[i]
                    let keepCard = keepCards[j]
                    
                    // 내카드 + 킵카드써서 코인 1개 소모
                    if myCard+keepCard == target {
                        round += 1
                        coin -= 1
                        point += 2
                        myCards.remove(at: i)
                        keepCards.remove(at: j)
                        continue outer
                    }
                }
            }
        }
        
        // 조건C: 코인이 2개이상 남아있고 킵해둔 카드에서 다 낼 수 있으면
        if coin >= 2 {
            for i in 0..<keepCards.count-1 {
                for j in i+1..<keepCards.count {
                    let keepCard1 = keepCards[i]
                    let keepCard2 = keepCards[j]
                    
                    // 킵카드 2개 써서 코인 2개 소모
                    if (keepCard1+keepCard2) == target {
                        round += 1
                        coin -= 2
                        point += 2
                        keepCards.remove(at: i)
                        keepCards.remove(at: i > j ? j : j-1)
                        continue outer
                    }
                }
            }
        }
        break
    }
    return round
}