알고리즘/백준(acmicpc.net) 문제풀이
-
1017번 : 소수 쌍알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 31. 16:11
https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 집합에 속한 임의의 원소 두개의 합이 소수가 되도록 모두 짝지었을 때 첫 번째 원소와 짝지은 원소들을 오름차순으로 출력하는 문제다. 아이디어, 구현 : 네트워크 플로우(이분매칭)으로 해결할 수 있었다. 하지만 조금 특이한 방식으로 해결했다. 먼저, 모든 수를 두개로 늘려서 짝지을 첫번째 원소, 짝지을 두번째 원소로 나누었다. 첫 번째 원소는 제외하..
-
2123번 : 인간 탑 쌓기알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 29. 14:11
https://www.acmicpc.net/problem/2123 2123번: 인간 탑 쌓기 N (1 ≤ N ≤ 50,000) 명의 곡예사들로 인간 탑을 쌓으려고 한다. 한 사람이 한 층을 이루게 되어, 탑은 총 N층이 된다. 어떤 층에 있는 사람은 그보다 높은 층에 있는 모든 사람들의 몸무게의 합만큼 www.acmicpc.net 곡예사들의 위험도 중 가장 큰 값이 가장 작아지게 배치하는 문제이다. 아이디어 : 주어진 곡예사들 중 가장 밑에 깔릴 하나를 구해야 한다는 느낌으로 접근한다. 모든 곡예사들에 대해 만약 그 곡예사가 가장 밑에 깔린다면 위험도는 얼마나 될지 구해본다. 구한 위험도 중 가장 작은 값을 갖고 있는 곡예사가 가장 밑에 깔린다. 밑에 깔린 곡예사는 이제 제외시키고 남은 곡예사들 중 가장..
-
1422번 : 숫자의 신알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 22. 15:53
https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net K개 수 중 N개를 중복으로 뽑아서 가장 큰 수를 만드는 문제다. (단 모든 수를 다 써야 함) 아이디어 : 숫자들을 잘 정렬하는 문제다. 우선 이 숫자들을 모두 문자열로 취급 할 것이다. 모든 문자열을 정렬해서, 순서대로 출력할 것이다. 출력할 때, 길이가 가장 긴 문자열은 N-K+1번만큼 연속으로 출력해준다. 구현 : 문자열 x와 문자열 y의 우선순위를 비교할 때, x+..
-
1369번 : 배열값알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 22. 14:24
https://www.acmicpc.net/problem/1369 1369번: 배열값 첫째 줄에 배열의 크기를 나타내는 자연수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 배열에 적힌 수를 나타내는 정수가 각각 N개씩 빈 칸을 사이에 두고 들어온다. 입력되는 정수는 www.acmicpc.net (1,1) ~ (N,N) 도달 중 만나는 수들을 곱할 때 뒤에 생기는 0의 최솟값을 구하는 문제다. 아이디어 : 뒤에 생기는 0의 개수라는 것은, 곧 2와 5의 개수 중 최솟값이라는 소리다. 따라서 2의 개수와 5의 개수에만 집중해보자. 최솟값을 구하려면, 2를 최소로 만들거나, 5를 최소로 만들어야 한다. 어떤 칸에 도달하려면, 위에서 내려오거나, 왼쪽에서 와야한다. 여기까지 dp식을 세울 ..
-
1154번 : 팀 편성알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 16. 19:55
https://www.acmicpc.net/problem/1154 1154번: 팀 편성 첫째 줄에 학생 수를 나타내는 자연수 N이 주어진다. (N≤1,000) 편의상 각 학생들은 1부터 N까지 번호가 붙어 있다고 가정한다. 둘째 줄부터 각 줄에 두 개의 자연수 a와 b가 빈 칸을 사이에 두고 주 www.acmicpc.net 학생들을 주어진 조건에 따라 두 그룹으로 나누는 문제이다. 아이디어 : 어떤 학생과 친구가 아니라는 것은, 무조건 그 친구와 다른 그룹이어야 한다는 것이다. 그렇다면, 답이 나오는 상황이라고 가정했을 때, 모든 학생에 대해서 해당 학생과 친구가 아닌 학생들을 전부 그룹으로 묶는 과정을 반복하면, 최종적으로는 두 그룹으로 나뉘어지게 될 것이다. 그 두 그룹에 대해 검증을 한번 더 하면,..
-
1131번 : 숫자알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 14. 20:30
https://www.acmicpc.net/problem/1131 1131번: 숫자 자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다. 이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … www.acmicpc.net i부터 시작해서 나열되는 수들 중 가장 작은 수의 합을 구하는 문제이다. 아이디어 : 그래프로 생각한다. 수 하나에서 시작하여 일정 수들을 거치면 항상 사이클이 생기는 것을 파악했다. 따라서 사이클에 속해있는 수들은 항상 똑같은 dp값을 가지고, 그게 아닌 수들만 따로 예외처리 해준다. 구현 : 먼저 p배열엔 0~9의 K제곱을 저장해준다. nxt엔 ..
-
1125번 : 바닥 장식알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 12. 18:49
https://www.acmicpc.net/problem/1125 1125번: 바닥 장식 방 바닥을 꾸미려고 한다. 다음과 같이 1×5 크기의 나무 판으로 만든 무한한 패턴의 평면을 생각해보자. 가장 왼쪽 위 좌표는 (0,0)이고, X좌표는 왼쪽에서 오른쪽으로 증가하고, Y좌표는 위에서 www.acmicpc.net 어떠한 구역에서 바닥 장식 크기마다 개수를 다 구해주고, 그 개수들을 이용해서 1x5 나무 판을 최소한으로 사야하는 문제다. 아이디어 : 첫 번째. 1x1, 1x2, 1x3, 1x4, 1x5 타일이 각각 몇개씩 필요한지 찾는다. 두 번째. 구매해야하는 1x5타일 개수의 최소값을 찾는다. 우선 주어진 구역보다 작은, 5x5 격자에 딱 맞는 직사각형을 하나 더 찾는다. 문제의 예시에선 저 보라색 ..
-
18186번 : 라면 사기 (Large)알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 20:25
https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 18185번과 매우 유사한 문제다. 2022.01.09 - [sunrin] - 18185번 : 라면 사기 (Small) 아이디어 : 다만, 한가지가 다르다. B와 C가 주어졌는데, 18185에서는 비용이 3, 5, 7로 연속3개의 공장에서 사는게 무조건 이득이었다. 하지만, 18186에서는 2, 1002, 2002 이런식으로 주어질 수도 있다. 즉, 모든 라면을 B로 사는 케이스..
-
18185번 : 라면 사기 (Small)알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 20:11
https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 연속된 1개 공장에서 라면을 사면 비용 3, 연속된 2개 공장에서 라면을 사면 비용 5, 연속된 3개 공장에서 라면을 사면 비용 7 의 비용을 내고 라면을 살 수 있을 때, 최소 비용을 구하는 문제였다. 아이디어 : 접근은 dp였다. i번째까지 최적화된 배열이 있을 때 i+1번째를 최적화 시키는 방법은 뭐가 있을까? 먼저 라면을 사는 방법은 총 3가지이다. i+1에서만 비용 3 ..
-
1071번 : 소트알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 19:18
https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 문제는 단순하다. A[i] + 1 != A[i+1] 을 만족하도록 모든 수를 다시 배치하는 것이다. 아이디어 : 두 수를 비교해서 위치를 바꾸는 일반적인 정렬 방식은 사용하지 않는다. 수들을 처음부터 하나하나 다시 배치하는 아이디어로 접근한다. 우선, 수를 하나 택한다고 생각해보자. 이 수를 뺀 나머지 수들을 이용해서 절대로 배열을 완성할 수 없다면, 그 수를 택할 수 없다. 반대로 말하면 -> ..