1463 - 1로 만들기
import Foundation
var n:Int = Int(readLine()!)!
func make_One(_ n:Int) -> Int{
// 3 이하
if(n==1){return 0}
else if(n==2){return 1}
else if(n==3){return 1}
// 4 이상
var solution_makeOne:[Int] = Array(repeating: 0, count: n+1)
solution_makeOne[1] = 0
solution_makeOne[2] = 1
solution_makeOne[3] = 1
for i in 4...n {
solution_makeOne[i] = solution_makeOne[i-1] + 1
if(i%3 == 0) {solution_makeOne[i] = min(solution_makeOne[i],solution_makeOne[i/3] + 1)}
if(i%2 == 0) {solution_makeOne[i] = min(solution_makeOne[i],solution_makeOne[i/2] + 1)}
}
return solution_makeOne[n]
}
print(make_One(n))1부터 n까지 차례대로 1로 만드는 연산의 최솟값을 모두 구하며
DP를 이용하는 풀이이다.
경우 1 - DP[n]에서 1을 빼는 경우
Dp[n-1]+1
경우 2 - N을 2로 나눌 수 있는 경우
DP[N/2]+1
경우 3-N을 3으로 나눌 수 있는 경우
DP[N/3]+1
위 식을 이용해 1부터 N까지 Memoization으로 구해가면 된다
10844 - 쉬운 계단수
import Foundation
var n:Int = Int(readLine()!)!
var num_Count:[Int] = Array(repeating: 1, count: 10)
num_Count[0] = 0
//n이 1일때 끝자리의 수의 개수 0인 경우 0개, 나머지(1~9)는 1개
func dp(_ n:Int) -> Int{
if(n == 1){ return 9 }
var tmp_past:Int = 0, tmp_now:Int = 0
for _ in 2...n { // 2 부터 n 단계까지 memoization
for i in 0...9 { // 각 단계의 끝자리가 i인 수를 모두 count하는 for
if i == 0 {tmp_now = num_Count[0]; num_Count[0] = num_Count[1]%Int(1e9)}
else if i == 9{ num_Count[9] = tmp_now%Int(1e9) }
else {
tmp_past = tmp_now
tmp_now = num_Count[i] // 전 단계의 끝자리가 i인 수를 변경에 대비해 tmp에 저장
num_Count[i] = (tmp_past + num_Count[i+1])%Int(1e9) //전 단계의 끝자리가 i-1인 수 와 i+1인 수의 갯수의 합
}
}
}
return num_Count.reduce(0,+) % Int(1e9)
}
print(dp(n))
각 끝 자리 수의 개수를 배열에 넣는 것이 핵심이다.
N일때는 n-1의 수를 비교하며 N일때 배열을 채운다.
N일때 2를 구한다면 n-1일때 dp[1]과 dp[0]을 더하여 채운다.
이런 방식으로 1 자리부터 n 자리까지 구해간다.
2156 - 포도주 시식
import Foundation
var n:Int = Int(readLine()!)!
var dp:[Int] = [Int](repeating: 0, count: n+1)
var check:[Bool] = [Bool](repeating: false, count: n+1)
var wine:[Int] = [Int](repeating: 0, count: n+1)
for i in 1...n { wine[i] = Int(readLine()!)! }
func max_Wine(_ n:Int) -> Int {
dp[1] = wine[1]
if(n==1){return dp[1]}
dp[2] = wine[1] + wine[2]
if(n==2){return dp[2]}
for k in 3...n {
dp[k] = max(dp[k-1], dp[k-2]+wine[k], dp[k-3]+wine[k-1]+wine[k])
}
return dp[n]
}
print(max_Wine(n))
이러한 방식으로 1부터 와인잔을 점차 늘려 N까지 최적의 값을
구한다.
11053 - 가장 긴 증가하는 부분 수열
import Foundation
var n:Int = Int(readLine()!)!
var num_Array = readLine()!.split(separator: " ").map{Int($0)!}
var increase:[Int] = [Int](repeating: 1, count: n)
var result:Int = 1
for index in 1..<n {
for i in 0..<index {
if(num_Array[i] < num_Array[index]) {
increase[index] = max(increase[index], increase[i]+1)
}
}
result = max(result,increase[index])
}
print(result)
11054 - 가장 긴 바이토닉 부분 수열
import Foundation
var n:Int = Int(readLine()!)!
var num_Array = readLine()!.split(separator: " ").map{Int($0)!}
var num_reverse = (num_Array.reversed() as [Int])
var increase:[Int] = [Int](repeating: 1, count: n)
var decrease:[Int] = [Int](repeating: 1, count: n)
var result:Int = 1
for index in 1..<n {
for i in 0..<index {
if(num_Array[i] < num_Array[index]) {
increase[index] = max(increase[index], increase[i]+1)
}
if(num_reverse[i] < num_reverse[index]) {
decrease[index] = max(decrease[index], decrease[i]+1)
}
}
}
decrease = decrease.reversed() as [Int]
for i in 0..<n {
result = max(result,increase[i]+decrease[i]-1)
}
print(result)이 문제는 LIS를 중첩하면 된다.
전 문제처럼 LIS를 하고 뒤에서부터 거꾸로 LIS를 하여 두 LIS 값을 더하면 된다.
거꾸로 LIS를 하기 위해서는 배열을 reversed를 해서 거꾸로 돌려 LIS를 구한다.
2565 - 전깃줄
import Foundation
typealias E = (A: Int,B: Int) // A 기둥 B 기둥
var n:Int = Int(readLine()!)!
var result:Int = 1
func electroLine() {
var line = [E]()
var length = Array(repeating:1, count: n)
for _ in 0..<n
{
let input = readLine()!.split(separator:" ").map{Int(String($0))!}
line.append((input[0],input[1]))
}
line.sort {
if $0.A < $1.A
{
return true
}
return false
}
for index in 0..<n {
for i in 0..<index {
if(line[index].B > line[i].B) {
length[index] = max(length[index],length[i] + 1)
}
}
result = max(result, length[index])
}
print(n-result)
}
electroLine()사실상 LIS 문제이다.
한쪽을 정렬한다음 LIS를 하여 가장 긴 증가하는 수열을 만들면 된다.
이유는 오름차순으로 선을 이어지도록 하면 선끼리 교차되지 않기 때문이다.
9251 - LCS
이 문제에서 한 문자열과 다른 문자열의 한 문자씩 비교하며 늘려가는 게 핵심이다.
핵심은 만약 비교하는 문자가 같다면
str1의 i-1까지와 str2의 j-1까지의 최적의 값에서 +1을 하고
하지만 비교하는 문자가 다르다면
Dp[i-1][j] or Dp[i][j-1]
(이때 Dp[i-1][j]를 비교하는 이유는 j가 추가되었기 때문에 비교하는 문자가 달라도 j로 인해 최댓값이 달라졌을 가능성이 있기 때문이다.)
import Foundation
var str1 = Array(readLine()!)
var str2 = Array(readLine()!)
var str1_size:Int = str1.count
var str2_size:Int = str2.count
var LCS:[[Int]] = Array(repeating: Array(repeating: 0, count: str2_size+1), count: str1_size+1)
str1.insert("z",at: 0) //쓰레기 값 (1부터 사용하기 위함)
str2.insert("z",at: 0) //쓰레기 값
for i in 1...str1_size {
for j in 1...str2_size {
if(str1[i] == str2[j]){
LCS[i][j] = LCS[i-1][j-1]+1
}
else{
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
}
}
}
print(LCS[str1_size][str2_size])실패한 코드
import Foundation
var str1 = Array(readLine()!)
var str2 = Array(readLine()!)
var str1_size:Int = str1.count
var str2_size:Int = str2.count
var LCS:[Int] = [Int](repeating: 0, count: str2_size)
var max_num:Int = 1
for str1_index in 0..<str1_size {
for str2_index in 0..<str2_size {
max_num = 1
if(str1[str1_index] == str2[str2_index]){
for i in 0..<str2_index{
max_num = max(max_num, LCS[i]+1)
}
LCS[str2_index] = max_num
}
}
}
print(LCS.max()!)이 코드는 같은 값을 만나면 배열에서 만나기 전까지의 최대의 +1을 LCS에 넣어준다.
하지만 이 방법의 문제는 비교하는 문자가 두 개 이상일 경우 문제가 발생했다
한 번 같은 값을 만나 LCS의 값을 넣어주고 또 다시 같은 문자를 만나면 전에 같은 값을 만나 값을 넣어준 LCS에 의해 이상한 값이 들어갈 수 있다.
예상 해결책: LCS를 2차원 배열로 만든다면 해결될 것 같다.
12865 - 평범한 배낭
이 문제의 핵심은 포함하는 item을 하나 씩 늘려가고 배낭 용량을 1씩 늘려가며 각 값으로 점화식을 통해 최적의 값을 구해나가는 것이다.
경우 1) 해당 아이템이 들어갈 공간이 없는 경우
해당 아이템을 제외했을 때 최적의 값
경우 2) 해당 아이템이 들어갈 공간이 있는 경우
해당 아이템을 제외했을 때 최적의 값 or 해당 아이템의 가치 + P[n-1][W-해당아이템의 무게]
import Foundation
var input:[Int] = readLine()!.split(separator: " ").map{Int($0)!}
var N = input[0]
var W = input[1]
var weight = [Int](repeating: 0, count: 0)
var value = [Int](repeating: 0, count: 0)
for _ in 0..<N {
var input:[Int] = readLine()!.split(separator: " ").map{Int($0)!}
weight.append(input[0])
value.append(input[1])
}
var Knap:[[Int]] = Array(repeating: Array(repeating: 0, count: W+1), count: N+1)
for i in 1...N {
for j in 1...W {
if(weight[i-1] <= j) {
Knap[i][j] = max(Knap[i-1][j], Knap[i-1][j-weight[i-1]] + value[i-1])
}
else {
Knap[i][j] = Knap[i-1][j]
}
}
}
print(Knap[N][W])
반려묘 하루 velog