Algorithm3 [백준 / BOJ] A → B - 16953 (Python) 문제 : https://www.acmicpc.net/problem/16953 주어진 두가지의 연산을 이용해서 자연수 A를 B로 변환할 때, 필요한 연산 횟수의 최솟값을 구하는 문제이다.A에서 B로 도달하는 것이 불가능할 수도 있으며, 이러한 경우 -1을 출력한다. (B > A로 주어진다.) 풀이크게 두가지 방법으로 나눌 수 있다. 문제에서 의도한 풀이는 아마 BFS를 활용한 풀이로 짐작된다. 그러나 그리디한 방법을 사용하면 BFS보다 더욱 빠르게 처리할 수 있다. 1. 지문을 자세히 보면, 두가지 사실을 알 수 있다. 둘 중 어떤 연산을 거쳐도 항상 수는 증가하며, 한번의 연산을 거치면 마지막 자리는 항상 1이거나, 짝수라는 것이다. 2. 위와 같은 사실을 통해 다시 생각해보면, A → B가 아닌.. 2025. 1. 25. [백준 / BOJ] 네 개의 소수 - 1153 (Java) 문제 : https://www.acmicpc.net/problem/1153 임의의 자연수 N에 대해서, 해당 수를 4개 소수의 합으로 표현하는 문제이다.4개의 소수 중, 중복인 수가 있을 수 있으며, 답이 여러가지인 경우가 있을 수 있다, 그 중 하나만 출력하면 된다. 풀이1. 문제의 4개의 소수를 'N을 구성하는 수'라고 하자. N을 구성하는 수는 모두 소수이므로, 우리는 자연수 중 어떤 수가 소수인지 알아야한다. 주어지는 N의 범위가 크기 때문에 에라토스테네스의 체를 이용해 N이하의 자연수 범위에서의 소수 여부를 저장하는 테이블을 구하자. 2. 문제에서 의도한 정석적인 풀이는 아닐 수 있지만, 필자는 골드바흐의 추측을 이용해 해결하였다. 골드바흐의 추측이란, '4이상의 모든 짝수는 두 소수의 합.. 2025. 1. 24. [백준 / BOJ] RGB거리 - 1149 (Java) 문제 : https://www.acmicpc.net/problem/1149 서로 인접한 집끼리 서로 다른 색(3가지 색을 사용할 수 있다)으로 칠할 때, 최소 비용을 구하는 문제이다. 입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 풀이나이브하게 모든 조합을 모두 탐색한다고 생각해보면 O(3^N)의 복잡도를 가진다. N은 최대 1,000이므로 모든 조합을 탐색하는 것은 불가능한 것을 알 수 있다. 해당 문제는 DP를 활용하여 해결할 수 있다. i 번째 집을 칠할 때, i-1번째 집까지 칠한 상태를 참고하는 방식이다... 2025. 1. 23. 이전 1 다음
