[Python] 2295번 세 수의 합
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 23/12/28 중간에서 만나기(MITM)으로 안 풀어도 집합으로 쉽게 풀 수 있는 문제이다. 나는 중간에서 만나기 알고리즘 연습을 위해 그 방법으로 문제를 해결했다. 첫번째 문제 접근 방식: MITM으로 해결했다. 세 수의 합이 최대가 되도록 하려는 것이 우리의 목적이고, 그 세 수의 합 또한 기존 배열에 존재해야 한다. 나는 두 개로 분할했는데,..
[Python] 11967번 불켜기
https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 23/12/30 BFS 응용 문제로, 생각했던 풀이 방법보다 더 쉬운 방법이 있어서 글을 써본다. 초반 문제 접근 방식: 초반에 접근했던 문제 방식은 BFS를 한 번만 돌도록 하는 방식이었다. 문제를 보면, 특정 방에서 다른 방들의 스위치를 킬 수 있다고 했다. 그리고 스위치가 켜져 있는 방만 출입할 수 있다고 했고, 방에서 방으로 움직일 때에..
[Python] 15573번 채굴
https://www.acmicpc.net/problem/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 23/12/31 2023년 마지막 날에 해결한 문제로, BFS와 이분 탐색을 섞은 파라메트릭 문제이다. 파라메트릭 서치 연습으로 아주 적절한 문제인 듯 하다. 문제 접근 방식: 문제에서 요구하는 것은 최솟값을 요구하고 있고, 이 값은 특정 값 이상을 넘어가는 최솟값이므로 파라메트릭 서치를 통해 구현할 수 있다. 채굴기의 성능 $D$와 광산의 모습을 입력으로 받아서 BFS를 통..