문제 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 입력받은 자릿수의 모든 수를 차례대로 소수 판정하는 것은 시간이 오래걸린다. 대신, 신기한 소수는 왼쪽의 한 자리 수부터 소수여야 한다는 점을 이용하여 경우의 수를 줄일 수 있다. 백트래킹을 이용해 현재 소수인 수들만 다음 자리수를 더한 소수를 찾는 탐색을 진행하면된다. 먼저 신기한 소수가 되려면 첫째 자리 수가 소수인 2, 3, 5, 7 중 하나여야 한다. 그 외의 수로 시작하는 수는 다음 단계로 진행하지 않는다. 예를 들어 첫째 자리가 ..

문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 백트래킹을 사용하여 해결할 수 있다. 백트래킹은 가능한 모든 경우의 수를 탐색하면서 답을 찾는 알고리즘으로 재귀 함수를 이용한다. 재귀 함수에서는 현재 선택한 재료로 만들어진 음식의 신맛과 쓴맛을 계산하고, 두 맛의 차이의 최소값을 갱신한다. 이후 다음 재료를 선택하고 다시 재귀적으로 함수를 호출한다. 선택한 재료는 방문 처리를 하여 중복 선택을 방지한다. 모든 가능한 조합을 탐색한 후에 최소값을 출력한다. 코드 import ko..

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 이 문제는 5명의 친구관계가 연결되어 있는 것을 찾는 문제로, DFS와 백트래킹을 이용하여 depth가 5인 관계를 찾으면 된다. 먼저, 친구관계를 입력받아 양방향으로 연결된 그래프를 생성한다. 그리고 모든 노드에 대한 DFS 탐색을 수행한다. DFS 탐색은 백트래킹을 이용하여 방문했던 노드에서 연결된 노드가 있을 경우 방문 체크를 해준 뒤 DFS를 수행한다. DFS 수행 이후 방문한 노드의 상태를 방문하지 않은 것으로 다시 바꿔준다. 탐색 중 DFS의 depth가 5가 되는 경우, 5명의 친구가 연결되었다고 판단하고 check 변수를 true로 만들어 준다..

문제 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 풀이 부등호를 만족하는 최소와 최대 정수를 백트래킹으로 찾는 문제이다. 입력받은 부등호에 따라 올바른 숫자를 선택하고 재귀적으로 탐색을 진행한다. 가장 먼저 완성된 답이 최소 정수, 가장 나중에 완성된 답이 최대 정수가 되는 것으로 각각 출력해주면 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val num = br.readLine(..

문제 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출..