[백준] (Swift) 1679번 - 숫자놀이 (dp)

🟠 문제링크

https://www.acmicpc.net/problem/1679

1679번: 숫자놀이

 

🟠 풀이방식

인터넷을 보니까 dp, dfs 등 다양한 방식으로 풀 수 있는 문제 같았다. 나는 그냥 가장 먼저 떠올랐던 dp 로 문제를 풀었다.

dp 에서 가장 중요한 것은, 해당 인덱스에 어떤 value값을 넣느냐를 결정하는게 가장 중요하다. 나또한 여기서 어떻게 넣을지 많이 고민했던 것 같다.

우선 dp[i] 라고 쳤을때, i번 더해서 나올 수 있는 수들을 dp 안에 넣어주었다. 그니까, 수들이니까 array 형태로 value 값을 넣어주었다. 예제로 예를 들면, 1과 3이 1번더해서 나올 수 있는 수이니까, dp[1] = [1, 3] 이렇게 넣어준 것이다.

자세한 풀이 방법은 아래와 같다.

 

🟠 메모리 초과 코드

왜 메모리 초과가 났을까 생각해보니까, 위 내가 그린 그림처럼, dp에 모든!!! 값들을 중복해서 넣어주고 있었다. 여기서 중복을 걸러주지 않아서 메모리가 너무 방대해지니까 메모리초과가 난 것 같아서수정했다.

//
//  main.swift
//  Algorithm
//
//  Created by LeeJiSoo on 2022/07/28.
//

import Foundation

let n = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = Int(readLine()!)!
var dp = Array(repeating: [Int](), count: k+1)
var visited = Array(repeating: false, count: (nums.max()! * k)+1)

for num in nums {
    visited[num] = true
    dp[1].append(num)
}

for i in 2..<k+1 {
    let previous = dp[i-1]
    for p in previous {
        for num in nums {
            visited[num+p] = true
            // ✅ 여기서 너무 모든 수들을 dp에 때려박고있었다.
            dp[i].append(num+p)
        }
    }
}

for j in 1..<(nums.max()!*k)+1 {
    if visited[j] == false {
        print(j % 2 == 0 ? "holsoon win at \(j)" : "jjaksoon win at \(j)")
        break
    }
}

 

🟠 전체코드 - 메모리초과 해결

dp.contains() 를 이용해서 dp 에 먼저 값이 있는지 판단해주고, 없을 경우에만 dp 에 넣어주었다. 

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1679_%EC%88%AB%EC%9E%90%EB%86%80%EC%9D%B4/main.swift

GitHub - deslog/Algorithm

//
//  main.swift
//  Algorithm
//
//  Created by LeeJiSoo on 2022/07/28.
//

import Foundation

let n = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = Int(readLine()!)!
var dp = Array(repeating: [Int](), count: k+1)
var visited = Array(repeating: false, count: (nums.max()! * k)+1)

for num in nums {
    visited[num] = true
    dp[1].append(num)
}

for i in 2..<k+1 {
    let previous = dp[i-1]
    for p in previous {
        for num in nums {
            visited[num+p] = true
            if !dp[i].contains(num+p) {
                dp[i].append(num+p)
            }
        }
    }
}

for j in 1..<(nums.max()!*k)+1 {
    if visited[j] == false {
        print(j % 2 == 0 ? "holsoon win at \(j)" : "jjaksoon win at \(j)")
        break
    }
}