Jenikeju

내가 푼 풀이

- 로프를 모두 사용하지 않아도 된다.

- 주어진 로프를 최대로 들수있는 중량이 큰 순으로 정렬한다.

- 로프가 추가되면, 추가된 로프의 중량값 x 로프의 갯수 = 버틸 수 있는 중량 이된다.

- 갱신한 값 출력

• [15, 10, 5] 로프 1개일때, 최대중량: [15] ---> 15
• [15, 10, 5] 로프 2개일때, 최대중량: [15,10] ---> 10 X 2 = 20 (정답)
• [15, 10, 5] 로프 3개일때, 최대중량: [15,10,5] ---> 5 X 3 = 15 

import Foundation

let count = Int(String(readLine()!))!
var arr = [Int]()

for i in 0..<count {
    let num = Int(String(readLine()!))!
    arr.append(num)
}
arr.sort{ $0 > $1}
var max = arr[0]

if arr.count == 1 {
    print(max)
} else {
    for i in 1..<arr.count {
        if max < arr[i] * (i+1) {
            max = arr[i] * (i+1)
        }
    }
    print(max)
}

내가 푼 풀이

- 그리디의 대표적인문제로, 돈의 크기가 큰순으로 최대한 많이 거슬러주면된다.

import Foundation

var money = 1000 - Int(String(readLine()!))!
var arr = [500, 100, 50, 10, 5, 1]
var result = 0

for i in arr {
    if i <= money {
        var num = money / i
        result += num
        money -= i * num
    }
}
print(result)

내가 푼 풀이

- 문제에서는 B를 재배열 하면 안된다고 했지만, 구하는 수는 S의 최솟값이다.

- 배열 A를 오름차순, 배열 B를 내림차순으로 정렬하여 서로 곱한값을 모두 합하면 최솟값이다.

import Foundation

let count = Int(String(readLine()!))!
var arrA = readLine()!.split(separator: " ").map{ Int(String($0))! }
var arrB = readLine()!.split(separator: " ").map{ Int(String($0))! }
var sum = 0
arrA.sort{ $0 < $1}
arrB.sort{ $0 > $1}

for i in 0..<count{
    sum = sum + (arrA[i] * arrB[i])
}
print(sum)

내가 푼 풀이

- 식의 값 최소로 만드는방법은 음수의 값을 최대로 만들면된다.

- 처음숫자는 무조건 양수이다.

- 문자열로 저장해서 음수(-) 가 나온다면, 그 이후로 나오는 모든 숫자는 빼주면 된다.

import Foundation

var str = Array(readLine()!).map{String($0)}
var sum = 0
var isSub = false
var numArr = [String]()

for i in str {
    if Int(i) != nil {
        numArr.append(i)
    } else {
        if isSub {
            sum -= Int(numArr.joined(separator: ""))!
            numArr = []
        } else {
            sum += Int(numArr.joined(separator: ""))!
            numArr = []
        }
        
        if i == "-" {
            isSub = true
        }
    }
}

if isSub {
    sum -= Int(numArr.joined(separator: ""))!
} else {
    sum += Int(numArr.joined(separator: ""))!
}

print(sum)

내가 푼 풀이

- 시간이 오래걸리는 사람이 먼저 있으면 다음사람도 그 시간만큼 기다려야한다.

- 적게 걸리는사람의 순서가 앞이면 기다리는 시간의 최솟값이 된다.

import Foundation

let count = Int(String(readLine()!))!
var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}
var sortedArr = arr.sorted{ $0 < $1 }
var sum = 0

for i in 0..<sortedArr.count {
    var num = 0
    for j in 0...i {
        num += sortedArr[j]
    }
    sum += num
}

print(sum)

내가 푼 풀이

- dp[i][j] = 길이 i인 문자 s1과 길이 j인 문자 s2 의 가장 긴 수열의 길이라 한다.

- s1, s2 문자열을 순회한다.

• 문자가 같으면 dp[i-1][j-1] + 1
• 문자가 다르면 max( dp[i-1][j], dp[i][j-1] )

import Foundation

var str1 = readLine()!
var str2 = readLine()!
var strArr1 = ["0"] + str1.map{String($0)}
var strArr2 = ["0"] + str2.map{String($0)}
var dp = Array(repeating: Array(repeating: 0, count: str1.count+1), count: str2.count+1)


for i in 1...str2.count {
    for j in 1...str1.count {
        if strArr2[i] == strArr1[j] {
            dp[i][j] = dp[i-1][j-1] + 1
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        }
    }
}

print(dp[str2.count][str1.count])

내가 푼 풀이

- N개의 카드를 구매하기 위해 돈을 최대로 지불하는 금액이 얼마인지 구하면 된다.

- P1 부터 PN까지 주어졌을때 이를 인덱스로 정해 N이 되는 중복조합을 구해서 이 중 최댓값을 구하게 했는데 시간초과가 떴다.

- n개의 카드를 구하는 경우의수를 다른 방법으로 구해보자.

- dp[n]: n개의 카드를 구매할때의 비용 최댓값 이라고 지정하자.

- n개의 카드를 구매할때 

• 1개가 들어있는 P1을 구매하는경우:  P1 + P(n-1)
• 2개가 들어있는 P2를 구매하는경우: P2 + P(n-2)
• 3개가 들어있는 P3를 구매하는경우: P3 + P(n-3)
• N개가 들어있는 PN을 구매하는경우: PN + P(n-n) = PN

이를 이용해서 최댓값을 저장한 dp를 재사용한다.

arr에 P1부터 PN의 비용을 저장한 후

• 1개가 들어있는 P1을 구매할때 비용의 최댓값: P1 + dp[n-1]
• 2개가 들어있는 P2을 구매할때 비용의 최댓값: P2 + dp[n-2]
• 3개가 들어있는 P3을 구매할때 비용의 최댓값: P3 + dp[n-3]
• N개가 들어있는 PN을 구매할때 비용의 최댓값: PN + dp[n-n] = PN

dp에 값을 저장할때 1부터 n까지 순회하며 최댓값을 갱신하여 저장한다.

import Foundation

let num = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: num+1)
var arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
arr.insert(0, at: 0)
dp[1] = arr[1]

if num > 1 {
    for i in 2...num {
        var max = 0
        for j in 1...i {
            let price = arr[j] + dp[i-j]
            if price > max {
                max = price
            }
        }
        dp[i] = max
    }
    print(dp[num])
} else {
    print(dp[1])
}

내가 푼 풀이

- 1 또는 00 타일을 깔 수 있다.

- dp[i]는 i자리의 타일 깔 수 있는 자리수라 한다.

• i자리 2진수의 첫번째 숫자가 1로 시작한다면, i-1자리 2진수의 가짓수를 최대로 센다.
• i자리 2진수의 첫번째 숫자가 00으로 시작한다면, i-2자리 2진수의 가짓수를 최대로 센다.

- 위 두가지 경우를 고려해 점화식을 세우면 dp[i] = dp[i-1] + dp[i-2] 가된다.

import Foundation

let count = Int(String(readLine()!))!

var dp = Array(repeating: 0, count: 1000001)
dp[1] = 1
dp[2] = 2
for i in 3..<dp.count{
    dp[i] = (dp[i-1] + dp[i-2]) % 15746
}

print(dp[count])