Swift 문제풀이

[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 76916 KB, 시간: 56 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 2일 17:20:29

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

    let N = Int(readLine()!)!
var dp:[Int] = [Int](repeating: 0, count: N + 1)
for i in 2 ..< N + 1 {
        dp[i] = dp[i - 1] + 1
        if i % 3 == 0 {
            dp[i] = min(dp[i], dp[i / 3] + 1)
        }
        if i % 2 == 0 {
            dp[i] = min(dp[i], dp[i / 2] + 1)
        }

    }
    print(dp[N])

[Silver III] 계단 오르기 - 2579

문제 링크

성능 요약

메모리: 69100 KB, 시간: 12 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 2일 20:47:47

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

    let T = Int(readLine()!)!
   var scores = [0]
   for _ in 0 ..< T {
       scores.append(Int(readLine()!)!)
   }
   var dp = Array(repeating: 0, count: T + 1)
   for i in 1 ..< T + 1 {
       if i == 1 {
           dp[1] = scores[1]
       } else if i == 2 {
           dp[2] = scores[1] + scores[2]
       } else if i == 3 {
           dp[3] = max(scores[3] + scores[1], scores[3] + scores[2])
       } else {
           dp[i] = max(scores[i] + scores[i-1] + dp[i - 3], scores[i] + dp[i-2])
       }
   }
   print(dp[T])