[Baekjoon] 1463번: 1로 만들기
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 과정 착안 자연수 $n=1, 2, ..., N$ 에 대해 $n=1$ 부터 반복문을 통해 $n$의 값을 증가시키면서 $3n, 2n, n+1$ 에 대한 연산 횟수의 값을 동적계획법(dynamic programming)을 통해 최솟값으로 갱신함으로써 문제를 해결하고자 했다. 구현 주어지는 수 $N$ 보다 큰 수에 대해서는 계산할 필요가 없으므로, $n=i$ 일 때, $3i, 2i, i+1$ 의 값이 $N$ 보다 작거나 같을 때에만 계산을 하도록 하였다. $3i, 2i, i+1$ 의 연산 횟수가 이미 계산되..
2023. 6. 15.
[Baekjoon] 1874번: 스택 수열
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해결 과정 착안 수열을 만들 수 있는지 확인하는 별다른 방법이 떠오르지는 않아, 문제에서 제시한 과정을 그대로 구현하여 문제를 해결하고자 하였다. 구체적으로는 아래와 같이 구현하고자 했다. 스택이 비어있거나 Top에 위치한 요소가 현재 수열의 항보다 작으면 push를 반복 (위 반복이 끝난 후) 스택의 Top에..
2023. 6. 12.