본문 바로가기

메모이제이션3

[BOJ] 백준 9019번: DSLR www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 이 문제는 D, S, L, R의 네 가지 명령을 사용해서 주어진 입력 A에서 B를 만드는데 필요한 최소 명령의 수와 그 명령이 무엇인지 출력하는 문제입니다. D 명령어는 수를 2배하며, S 명령어는 수에 1을 빼는 연산을 수행합니다. 또한 L 명령어는 왼쪽으로 시프트 후 맨 앞자리를 뒤로 위치시키며, R 명령어는 반대로 동작합니다. 아래의 예시를 참고해주세요. 1234 →L 2341 →L 341.. 2020. 10. 21.
[BOJ] 백준 1005번: ACM Craft 문제 링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 예제 그림은 4번 건물을 짓기 위하여 2번과 3번 건물이 모두 지어져야 하고, 2번과 3번을 짓기 위하여 1번 건물이 지어져야 하는 경우를 보여준다. 이때 4번 건물을 짓기위해 걸리는 최소 시간은 1->3->4 를 짓는 시간인 120초가 걸리게 된다. 즉, i번 건물까지 짓는 시간은 자신의 상위 건물(j..) 들 중 가장 오래 걸리는 시간에 영향을 받는다. 동적 계획법을 사용하여 dp[i]를 i번째 것물을 짓는 최소 시간이라고 한다면 아래 식으.. 2020. 6. 29.
[BOJ] 백준 2098번: 외판원 순회 TSP (traveling salesman problem) 로 잘 알려진 외판원 순회문제는 NP-Hard 문제로, 마을의 수 n에 대해 다항식의 형태로 복잡도가 계산될 수 없다. 그래서 N의 개수가 매우 적고, 비트마스크를 사용하여 방문한 마을을 1로 표기하여 001011 처럼 1,2,4 번째 마을을 방문했다를 표현할 수 있다. TSP는 시작점을 어느 마을로 하든 동일한 값이 나오기 때문에 시작 마을을 인덱스 0으로 편의상 둔다. if (state == (1 2020. 6. 25.