본문 바로가기

문제 해결/BOJ117

[백준] 등수 찾기 https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 그래프 탐색 문제입니다. 이 문제의 특징은 그래프를 2개를 만들어서 각각 그래프를 탐색해야한다는 것 입니다. 자기보다 잘한 사람들을 가르키고 있는 그래프(in_graph)와 자기보다 못한 사람(out_graph)을 가르키고 있는 그래프를 각각 만들고 X보다 잘한 사람을 찾기 위해 in_graph를 탐색하면 자기보다 등수가 높을 수 있.. 2023. 2. 24.
[백준] 게리 멘더링2 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 정말 정말 귀찮은 2차원 배열 시뮬레이션, 브루트포스 문제입니다. 모든 x, y, d1, d2 조합에 대해 각각의 구역의 인구수를 계산해주면 됩니다. 가장 어려웠던 부분은 구역을 나누는 부분인데 저는 다음과 같이 해결하였습니다. 1. 먼저, 5번 구역에 대해 처리를 먼저 해줍니다. 5번 구역에 대한 경계선을 미리 체크해주고 5번 구역의 경계 안에 있는 부분들도 체크해줍니다. 최상단 행과 최하단 행에는 .. 2023. 2. 23.
[백준] 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 시간초과로 고생을 꽤나 한 문제입니다. 처음에 접근은 BFS + 우선순위 큐를 사용하여 현재 위치에 도달할 수 있는 최소값만을 선택해서 dist 2차원 배열에 저장하는 방식으로 풀이했습니다. 하지만 이런 방식을 사용하면 우선순위 큐에 push하는데 O(log n)만큼의 시간이 소요되기 때문에 시간초과가 발생했습니다. 1. 제가 지나쳤던 부분은 BFS를 통해 탐색.. 2023. 2. 22.
[백준] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 정말 다시는 만나고 싶지 않은 문제.. CCTV의 감시구역을 배열로 복사해서 넘기면 상대적으로 간단하게 풀 수 있지만 시간속도나 메모리 사용 여부를 줄여보고자 배열을 복사하지 않고 감시 구역을 체크해주고 DFS에서 돌아오면 다시 복구시키는 방식으로 해결하고자 했습니다. 이런 방식으로 풀 때 주의해야할 실수들은 다음과 같습니다. 1) 복구시키는 과정에서 중복으로 감시받는 위치 다른 CCT.. 2023. 2. 21.
[백준] LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 제목 그대로 LCA 문제입니다. 일반적인 DFS로는 시간초과가 발생할 것 같아서 DP와 결합된 LCA알고리즘을 활용하여 풀이하였습니다. import sys from collections import defaultdict from math import log, ceil sys.setrecursionlimit(10 ** 6) # sys.stdin = open("input.txt", "r").. 2023. 2. 21.
[백준] 당근 훔쳐 먹기 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 간단한 정렬문제입니다. 당근들은 매일 pi만큼 맛이 증가하고 시작인 wi가 pi보다 항상 작거나 같기 때문에 pi가 큰 순으로 내림차순 정렬한 다음 t일, t - 1일, t - 2일.. 에 하나씩 먹어주면 가장 최대의 맛을 얻을 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.s.. 2023. 2. 20.
[백준] 정복자 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net MST를 구하는 문제입니다. 프림, 크루스칼로 MST를 구한 다음 증가하는 비용만큼을 추가해주면 됩니다. N개의 노드에서 MST를 선택하면 N - 1개의 간선을 선택하게 되고 증가하는 비용의 총합은 0 ~ N - 2의 합 * t이므로 MST의 간선의 합에 추가적으로 더해주면 됩니다. 프림 import sys, heapq from collections import defaultdict # sys.std.. 2023. 2. 19.
[백준] 같이 눈사람 만들래? https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 4개의 수중 2개씩 수를 더한 다음 합쳐진 2개의 수의 차이가 적게 되도록 해야합니다. 차이가 작아지려면 2개의 수를 합칠 때에 반드시 (가장 큰 수 + 가장 작은 수), (2번째로 큰 수 + 3번재로 큰 수)가 되어야한다는 점을 활용하여 풀이하였습니다. 눈덩이를 오름차순으로 정렬한 다음 가장 작은 수와 가장 큰 수를 각각 i, j가 가르키도록 합니다. 그리고 해당 .. 2023. 2. 18.
[백준] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE ans: ans_start = t ans = cnt + time[t] isUpdated = True # 답이 갱신된 적이 있고 값이 더 적어진다면 최장 기간이 끝난 것이므로 기록해준다. if isUpdated and cnt + time[t] < ans: ans_end = t isUpdated = False cnt += time[t] print(ans) print(ans_star.. 2023. 2. 17.

티스토리툴바