μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- RxSwift
- ios
- λ°±μ€
- combine
- Swfit
- ν¨μ€νΈμΊ νΌμ€
- swift
- MVVM
- TCA
- Flutter
- Kuring
- realm
- arkit
- reactorkit
- node.js
- rxcocoa
- BFS
- designpattern
- SnapKit
- BOJ
- XCTest
- tableView
- νλ‘κ·Έλλ¨Έμ€
- SwiftUI
- raywenderlich
- visionOS
- CollectionView
- UIKit
- Xcode
- Lv2
- Today
- Total
lgvv98
[Swift] BOJ 2158 ν¬λμ£Ό μμ λ³Έλ¬Έ
BOJ 2158 ν¬λμ£Ό μμ
β λΉμ·ν μ νμ μΌμ μ νμ΄λ³Έ κΈ°μ΅μ΄ μμ΄μ κΈλ°© νκ² λ€ νμλλ°, λ¬΄μ§ μ€λ κ±Έλ Έμ.
λ°±μ€ 2579λ² κ³λ¨μ€λ₯΄κΈ°μ λΉμ·νλ°, μ½κ° λ€λ₯Έ μ μ΄ μμ
κ³λ¨ μ€λ₯΄κΈ°μμλ λ§μ§λ§κ°μ 무쑰건 μ ννμ§λ§ ν¬λμ£Όλ λ§μ§λ§μ μ ννμ§ μμ μλ μμ.
λ¬΄μ¨ λ§μ΄λλ©΄
[100 100 1 1 100 100]μ κ²°κ³Όκ° μλ€κ³ νμ.
κ³λ¨ μ€λ₯΄κΈ° μκ³ λ¦¬μ¦μ μ μ©νλ©΄ 301μ΄ λμ€λ, ν¬λμ£Ό μμ λ¬Έμ μμλ 400μ΄ λμμΌ ν¨.
β μκ³ λ¦¬μ¦ μ κ·Όλ²μ°μ κ³λ¨ μ€λ₯΄κΈ°μ λ§μ°¬κ°μ§λ‘ ? X O? X O Oλ‘ λλμ΄μ μκ°νμ.? μ리λ dpλ°°μ΄μμ Oμ리λ 리μ€νΈμμ λ½κΈ°λ°λΌμ μ°λ¦¬λ μ νμμ λ§λ€ μ μλλ°, λμ리λ₯Ό iλΌκ³ κ°μ νμ μ
1. dp[i-2] + list[i]
2. dp[i-3] + list[i] + list[i-1]
μ΄λ κ² λκ°μ μ νμμ λ§λ€ μ μμ.
κ·Όλ° μ°λ¦¬λ λ§μ§λ§μ κ²½μ°μ λ°λΌμ μ ννμ§ μμ μλ μμ.κ·ΈλκΉ 3μ°μμ΄ λΆκ°νλ―λ‘ ? X O O Xμ κ²½μ°κ° μκΈ°λ κ²μ.dp λ°°μ΄μ κ°μ κ·Έ μΈλ±μ€κΉμ§λ νμ κ·Έ κ°μ΄ μ΅μ μ κ°μ μ ννλ€κ³ κ°μ νκ³ μμ.λ§μ½ dp[i]μ κ°μ΄ dp[i-1]κ³Ό κ°λ€λ©΄ μ΄λ€μλ―ΈμΌκΉ?λ°λ‘ dp[i]μ κ°μ΄ μ νλμ§ μμ μΌμ΄μ€μ. (list[i] > 0) κ·Έ μΌμ΄μ€μ κ²½μ°μλ λ§μ§λ§μ μ ννμ§ μμ.
λ€μ λ§ν΄μ μ΄λ²μ μ ννμ§ μμμΌλ©΄ μ΄μ (i-1)κΉμ§μ μ΅μ κ°μ΄ νμ¬(i)μ κ°μ κ°μ΄ λλ€.
μ¦ max(dp[i], dp[i-1])μ ν΅ν΄μ μ΄λ²μ μ νν μ§ λ§μ§μ λν κ²°μ μ ν μ μλ€.
λ°λΌμ λ§μ§λ§μ dp[i] μ κ°κ³Ό dp[i-1]κ°μ λΉκ΅ν΄μ λ ν° κ°μ dp[i]μ λ£μ΄μ€λ€.
π μ½λ
// https://www.acmicpc.net/problem/2156
import Foundation
struct b2156 {
static func run() {
// DPλ₯Ό μ΄μ©νμ¬ νμ΄μΌ ν©λλ€.
let input: Int = Int(readLine()!)!
var list = [Int]()
var dp = [Int](repeating: 0, count: input)
for _ in 0..<input {
list.append(Int(readLine()!)!)
}
if input >= 1 {
dp[0] = list[0]
}
if input >= 2 {
dp[1] = list[0] + list[1]
}
if input >= 3 {
dp[2] = max(list[0] + list[2], list[1] + list[2])
dp[2] = max(dp[2], dp[1])
for i in 3..<list.count {
dp[i] += max(dp[i-2] + list[i] , dp[i-3] + list[i] + list[i-1])
dp[i] = max(dp[i], dp[i-1])
}
}
// print(dp)
print(dp.max()!)
}
}
'μ½λ©ν μ€νΈ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Swift] BOJ 2178 λ―Έλ‘ νμ (0) | 2022.04.02 |
---|---|
[Swift] BOJ 10844 μ¬μ΄ κ³λ¨ μ (0) | 2022.04.02 |
[Swift] BOJ 1912 μ°μν© (0) | 2022.04.02 |
[Swift] νλ‘κ·Έλλ¨Έμ€ LV2. κ°μ₯ ν° μ (0) | 2022.04.02 |
[Swift] BOJ 1932 μ μ μΌκ°ν (0) | 2022.04.01 |