Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 깃헙
- Algorithm
- new int
- git status
- Git
- IOS
- 깃 명령어
- Cpp
- protocol 기본구현
- ios framework
- unreal dynamic framework
- 2차원배열
- github
- PS
- Problem Solving
- 리눅스 명령어
- C++
- 인프런
- 깃허브 가이드
- where Self
- 동적할당
- Unreal static Framework
- 백준
- 깃허브
- Swift
- embed&sign
- Unreal iOS
- Unreal iOS Framework
- 알고리즘
- 깃허브 사용법
Archives
- Today
- Total
Get Up & Code, MacKin Talk
[백준]1463_1로 만들기 본문
문항번호: 1로 만들기
1. 문제 분석
정수 X가 사용할 수 있는 연산
- X%3 == 0 -> X = X/3
- X%2 == 0 -> X = X/2
- X = X-1
2. 풀이 계획
- 입력 제한: 1<= N <= 10^6
- 출력 : 연산을 하는 횟수의 최솟값
- 풀이 방향
- 총 3가지의 연산이 존재.
- divide by 3
- divide by 2
- minus 1
- 총 3가지의 연산이 존재.
연산의 사용을 최소화하려고 한다.
BFS 알고리즘을 활용하고, 간선을 연산의 수로 생각한다면 해당 문제를 충분히 해결할 수 있을 것 같다.
-> BFS만으로 문제에 대한 해결책을 제시했을 때 시간 초과가 발생했다.
추가적인 조건을 주어야 하겠다.
9를 3으로 나눠 3이 되는 경우도 있지만,
9를 2로 나누고, -2를 하는 경우도 있고,
9에서 -6을 하는 경우도 3으로 도달할 수 있다.
즉, 이미 방문했던 노드는 더 이상 방문하지 않도록 해야 한다.
3. 계획 검증
문항 시간제한이 상당히 깐깐하다.
4. 소스 코드
import Foundation
let N = Int(readLine()!)!
var queue = [(value: Int, depth: Int)]()
var result = 0
let level = 0
queue.append((value: N, depth: level))
var checked = Array(repeating: false, count: N+1)
checked[N] = true
while true {
let current = queue.removeFirst()
if current.value == 1 {
result = current.depth
break
}
var nextNode = current.value / 3
if current.value % 3 == 0 && checked[nextNode] == false {
checked[nextNode] = true
queue.append((nextNode, current.depth+1))
}
nextNode = current.value / 2
if current.value % 2 == 0 && checked[nextNode] == false {
checked[nextNode] = true
queue.append((nextNode, current.depth+1))
}
nextNode = current.value-1
if checked[nextNode] == false {
checked[nextNode] = true
queue.append((nextNode, current.depth+1))
}
}
print(result)
5. 돌아보기
다이나믹 프로그래밍의 적용을 swift
에서 적용해본 것은 처음이다.
코드가 익숙해질 때까지 반복해야겠다.
중복 방문을 막기 전에는 시간 초과
가 발생했지만, 중복 발생에 대한 문제 해결 이후 시간 초과
를 해결할 수 있었다.
nextNode
라는 변수명은 추후에 수정한 부분이다.- 의미상 해석이 좋은 네이밍으로 풀이를 진행하는 게 좋을 것 같다.
tag: problem solving
다이나믹 프로그래밍
'IOS > 알고리즘 문제 풀이' 카테고리의 다른 글
[백준]1931_회의실 배정 (0) | 2021.11.01 |
---|---|
[백준]15652 N과 M(4) (0) | 2021.10.19 |
[백준]1966_프린터큐 (0) | 2021.10.11 |
[백준]11047_동전0 (0) | 2021.10.06 |
[백준]18830_좌표압축 (0) | 2021.10.06 |