๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ“– Problem Solution/Programmers

[Swift] 2022 KAKAO TECH INTERNSHIP ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๊ณต๋ถ€

by Fomagran ๐Ÿ’ป 2022. 8. 26.
728x90
๋ฐ˜์‘ํ˜•

Problem

 

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr


Solution

 

ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

 

1. ์•Œ๊ณ ๋ ฅ๊ณผ ์ฝ”๋”ฉ๋ ฅ์˜ ์ตœ๋Œ€์น˜๋ฅผ ๊ตฌํ•ด์ค€๋‹ค.

 

๋ฌธ์ œ๋ฅผ ๋ชจ๋‘ ํ’€ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ์•Œ๊ณ ๋ ฅ๊ณผ ์ฝ”๋”ฉ๋ ฅ์˜ ์ตœ๋Œ€์น˜๋ฅผ ์–ป๋Š” ๋‹ค๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋ฏธ๋ฆฌ ๊ตฌํ•ด์ค€๋‹ค.

 

    var maxAlp: Int = alp
    var maxCop: Int = cop
    
    problems.forEach {
        maxAlp = max(maxAlp,$0[0])
        maxCop = max(maxCop,$0[1])
    }

 

2. dp ๋ฐฐ์—ด์„ ์•Œ๊ณ ๋ ฅ + 1 , ์ฝ”๋”ฉ๋ ฅ + 1๊ฐœ์˜ ์ด์ค‘ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ์ค€๋‹ค.

 

๊ฐ ๋ฐฐ์—ด์˜ ๊ฐ’์€ ๋ฌด๋‚œํžˆ ํฐ ๊ฐ’(?)์œผ๋กœ ์„ค์ •ํ•ด ์ค€๋‹ค. (Int.max๋ฅผ ํ•˜๊ฒŒ ๋˜๋ฉด ๋’ค์— ํ•ด๋‹น ๊ฐ’์— +1์„ ํ•ด์ค„ ๋•Œ ์˜ค๋ฅ˜๊ฐ€ ๋‚จ)

 

๊ฐ€์žฅ ์ดˆ๊ธฐ๊ฐ’์€ 0์œผ๋กœ ์„ค์ •ํ•ด ์ค€๋‹ค.

 

    var dp: [[Int]] = Array(repeating:Array(repeating:10000,count:maxCop+1),count:maxAlp+1)
    dp[alp][cop] = 0

 

3. ์ตœ๋Œ€ ์•Œ๊ณ ๋ ฅ๊ณผ ์ตœ๋Œ€ ์ฝ”๋”ฉ๋ ฅ๊นŒ์ง€ dp์˜ ๊ฐ’์„ +1 ํ•˜์—ฌ ๋น„๊ตํ•œ๋‹ค.

 

dp์˜ ๊ฐ’์„ 1์”ฉ ๋Š˜๋ ค๊ฐ€ ์ฃผ๋ฉฐ ๋” ์ž‘์€ ๊ฐ’์œผ๋กœ ํ˜„์žฌ ๊ฐ’์„ ๊ฐฑ์‹ ํ•ด ์ค€๋‹ค.

 

    for currentAlp in alp...maxAlp {
        for currentCop in cop...maxCop {
            var minAlp = min(currentAlp+1,maxAlp)
            var minCop = min(currentCop+1,maxCop)
            dp[minAlp][currentCop] = min(dp[minAlp][currentCop],dp[currentAlp][currentCop] + 1)
            dp[currentAlp][minCop] = min(dp[currentAlp][minCop],dp[currentAlp][currentCop] + 1)
			...

 

4. ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋ฅผ ํ™•์ธํ•˜์—ฌ ํ•ด๋‹น ๋ฌธ์ œ์˜ ์•Œ๊ณ ๋ ฅ ์ฝ”๋”ฉ๋ ฅ์„ ๋”ํ•œ dp ์œ„์น˜๋ฅผ ๋น„๊ตํ•œ๋‹ค.

 

๋งŒ์•ฝ ํ˜„์žฌ ์•Œ๊ณ ๋ ฅ, ์ฝ”๋”ฉ๋ ฅ์ด ๋ฌธ์ œ์˜ ์ฝ”๋”ฉ๋ ฅ,์•Œ๊ณ ๋ ฅ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋ฏ€๋กœ,

 

ํ•ด๋‹น ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ ์ˆ˜๋ฅผ ํ˜„์žฌ ์•Œ๊ณ ๋ ฅ, ์ฝ”๋”ฉ๋ ฅ์— ๋”ํ•ด์ค€๋‹ค.

 

์ตœ๋Œ€ ์•Œ๊ณ ๋ ฅ, ์ฝ”๋”ฉ๋ ฅ์„ ๋„˜์–ด๊ฐˆ ์ˆ˜๋„ ์žˆ์œผ๋ฏ€๋กœ ๊ทธ ๋• ์ตœ๋Œ€๊ฐ’์œผ๋กœ ์„ค์ •ํ•ด ์ค€๋‹ค.

 

๊ทธ ๋‹ค์Œ ํ•ด๋‹น ์œ„์น˜์˜ ๊ฐ’๊ณผ ๋น„๊ตํ•˜์—ฌ ๋” ์ž‘์€ ๊ฐ’์œผ๋กœ ๊ฐฑ์‹ ํ•ด ์ค€๋‹ค.

 

            problems.forEach { problem in
                if currentAlp >= problem[0] && currentCop >= problem[1] {
                    minAlp = min(maxAlp,currentAlp+problem[2])
                    minCop = min(maxCop,currentCop+problem[3])
                    dp[minAlp][minCop] = min(dp[minAlp][minCop],dp[currentAlp][currentCop] + problem[4])
                }
            }
        }
    }

 

5. ์ตœ๋Œ€ ์•Œ๊ณ ๋ ฅ, ์ฝ”๋”ฉ๋ ฅ ์œ„์น˜๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

    return dp[maxAlp][maxCop]

Result

 

 

์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์•Œ๊ณ ๋ ฅ, ์ฝ”๋”ฉ๋ ฅ์˜ ์ตœ๋Œ€๊ฐ’์ด 150, ๋ฌธ์ œ์˜ ์ตœ๋Œ€๊ฐ’์ด 100์ด๋ฏ€๋กœ O(150*150*100)์ด ๋œ๋‹ค.

 

๊ณต๊ฐ„ ๋ณต์žก๋„๋Š” ์ฝ”๋”ฉ๋ ฅ ์•Œ๊ณ ๋ ฅ์˜ ์ตœ๋Œ€๊ฐ’์„ ์ €์žฅํ•˜๋ฏ€๋กœ O(150*150)์ด ๋œ๋‹ค.


Source Code

 

func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
    var maxAlp: Int = alp
    var maxCop: Int = cop
    
    problems.forEach {
        maxAlp = max(maxAlp,$0[0])
        maxCop = max(maxCop,$0[1])
    }
    
    var dp: [[Int]] = Array(repeating:Array(repeating:10000,count:maxCop+1),count:maxAlp+1)
    dp[alp][cop] = 0
    
    for currentAlp in alp...maxAlp {
        for currentCop in cop...maxCop {
            var minAlp = min(currentAlp+1,maxAlp)
            var minCop = min(currentCop+1,maxCop)
            dp[minAlp][currentCop] = min(dp[minAlp][currentCop],dp[currentAlp][currentCop] + 1)
            dp[currentAlp][minCop] = min(dp[currentAlp][minCop],dp[currentAlp][currentCop] + 1)
            
            problems.forEach { problem in
                if currentAlp >= problem[0] && currentCop >= problem[1] {
                    minAlp = min(maxAlp,currentAlp+problem[2])
                    minCop = min(maxCop,currentCop+problem[3])
                    dp[minAlp][minCop] = min(dp[minAlp][minCop],dp[currentAlp][currentCop] + problem[4])
                }
            }
        }
    }
    
    return dp[maxAlp][maxCop]
}
728x90
๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€