ℹ️ 문제 정보
| 플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
|---|---|---|---|---|---|
| 백준 | 31926 | 밤양갱 | 그리디 | 실버1 | Swift, Python |
🚀 나의 접근 방법
문제에서 주어진 행동은 아래와 같이 두 가지가 있다.
행동 1 : 알파벳 소문자 a부터 z 중에서 민우가 원하는 알파벳을 하나 골라서 지금까지 입력한 내용의 맨 뒤에 입력한다.
행동 2 : 지금까지 입력한 문자열의 연속된 부분 문자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면, ajouapcshake를 복사할 수도, apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.
위 행동에 맞춰 N=1 일 때를 생각해 보면 아래와 같이 총 10초가 걸린다.
N>=2 경우부터는 daldidalgo(빨간색)를 한 개(daldidalgo) 또는 여러 개씩(daldidalgodaldidalgo) 복사할 수 있다.
그러면 N=4일 경우를 생각해 보자. 결과는 아래와 같을 것이다.
이제 위 결과가 만들어지는 과정을 거꾸로 생각해 볼 것이다. 최소 시간을 구해야 하기 때문에 가능한 빨리 만들어야 한다. 즉, 복사를 최대한 활용해야 한다.
일단 마지막 daldidan(파란색)은 마지막에 생각하자.
그러면 위 N=4 일 때 전에는 아래와 같을 것이다. (복사, +1초)
또 위 상태 전에는 아래와 같다. (복사, +1초)
이제 남은 daldidalgo는 처음에 설명했듯이 8초에 걸려 완성된다. 그런데 아까 daldidan을 잠시 제외시켰다. 마지막 daldidan까지 포함 시키면 10초이다.
결과적으로 10 + 1 + 1 = 12초 걸리게 된다.
N이 다른 수일 경우가 궁금해질 것이다. 한 번 직접 그려보고 계산해 보자. 느낌이 올 것이다.
✍️ 나의 코드
Swift
let N = Int(readLine()!)!
var count = 0
var k = N
while k > 1 {
k /= 2
count += 1
}
print(10 + count)Python
N = int(input())
count = 0
k = N
while k > 1:
k = k // 2
count += 1
print(10 + count)🤔 회고 및 개선사항
첫 풀이
처음에는 아래와 같이 문제를 해결했다. 사실 원리는 위의 코드와 같다. 대신 접근을 위에서부터 하나, 아래에서부터 하나 차이이다.
import Foundation
let N = Int(readLine()!)!
var count = 8
var k = 1.0
while true {
let ans = N - Int(pow(2.0, k))
if ans == 0 {
count = count + Int(k) + 2
break
} else if ans < 0 {
count = count + Int(k) + 1
break
}
k += 1
}
print(count)
