29792번: 규칙적인 보스돌이 보스의 체력 $P$의 제한 $2.66 \times 10^{11}$와 드랍하는 메소 $Q$의 제한 $1\,596\,506$은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보 www.acmicpc.net 접근한 방법 이 문제는 배낭 알고리즘을 N번 수행해야 하는 문제입니다. 문제가 복잡해보일 수 있지만 배낭 알고리즘을 이해하고 있다면 풀이할 수 있습니다. 배낭 알고리즘은 제약 조건 아래에서 주어진 무게와 가치를 가진 여러 아이템 중에서 어떤 아이템을 선택하여 배낭에 담을지 결정하는 최적화 알고리즘입니다. 일반적으로 최대 가치를 얻고자 할 때 사용합니다. 저는 이런 변형 문제를 풀 때 헷갈리지 않도록 무게와..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 접근한 방법 이 문제를 풀기 위해선 두 가지 과정이 필요합니다. 1. 선거구를 나눌 두 개의 조합 2. 각 조합을 탐색하여 서로 연결되어 있는 지 확인 먼저 두 개의 조합(A, B)으로 나누기 위해서는 1개 조합, 2개 조합, ... (N / 2)개 조합을 먼저 구한 후(A) 전체 조합에서 A 원소들을 빼준 것을 (B)로 정합니다. 예를 들면 A = [1, 2, 3, 4]의 조합은 1개 조합일 때 -> A = 1. B = [1, 2, 3, 4] - A = 2, 3, 4 -> A = 2..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 접근한 방법 플로이드 워셜로 최단 경로를 구해 갱신하는 방법으로 접근합니다. 플로이드 워셜은 n^3 복잡도까지 커버할 수 있어서 표본 수가 적다면 가장 쉽고 간단하게 풀이할 수 있습니다. 각 정점을 순회하면서 중간 지점을 통해 경로하는 거리와 원래 놓여있는 거리 중 더 짧은 것으로 결정합니다. 최대한 중간지점을 통해 가지 않는 것이 거리가 1로 가장 짧으므로 회장 후보로 등록될 가능성이 클 것입니다. 탐색 후 각 정점마다 입력되어 있는 거리중 가장 먼 거리를 최..

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근한 방법 매 반복문을 돌며 BFS를 이용해 조건에 맞는 좌표를 후보지에 등록해두고 탐색이 끝나면 등록된 후보지들의 인구 수를 한꺼번에 변경해주는 방식으로 구현합니다. 1. while 문을 이용해 인구 이동 횟수를 카운트합니다. 2. 연합이 가능한 위치들을 넣을 후보 배열을 만들고 방문하지 않은 위치에 대하여 탐색을 시도합니다. 3. BFS탐색을 시도하여 방문하지 않았고 절댓값 차이가 L과 R 사이 값을 만족하는 위치가 있는 곳을 확인하여 후보지에..

18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 접근한 방법 완전탐색, 백트래킹 문제입니다. 장애물 3개를 놓을 수 있는 모든 경우의 수를 탐색합니다. 각 경우에서 선생님(T)으로부터 4방향을 모두 검사하여 학생(S)이 한명이라도 발견되는 경우 즉시 탐색을 멈춥니다. 발견되지 않으면 횟수를 카운트합니다. 카운트한 횟수와 선생님의 수가 일치할 경우 모든 감시를 피한 것으로 처리하고 그렇지 않은 경우는 피하지 못한것이 됩니다. Python import sys input = sys.stdin.readline..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 접근한 방법 다른 풀이방법이 많이 있지만 다익스트라 알고리즘으로 풀이합니다. 1번부터 마지막번 노드까지 각각 탐색 시작점을 설정하여 다른 노드까지의 최단 경로 차트를 만든 후 그 안에서 수색 범위(M)안에 해당하는 노드의 아이템 값(items[노드 번호])만 합산해서 최댓값을 구해주면 되는 문제입니다. 코드 풀이 (Python) import sys input = sys.stdin.readline n, m, r = map(int, input().split()) items..