Devlog

13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이 문제가 원래 우선순위 큐를 두개로 푸는게 정석이라는데 아마 이 문제 컨셉이 보석 도둑과 비슷한가 봅니다. 근데 저는 머리가 안좋아서 보석 도둑을 풀었을 때의 풀이법은 다 까먹었고, 다른 방법으로 풀었습니다. 저 "보석 도둑"도 시간 나면 복기해봐야겠군요. 아까도 얘기했지만 정석과 다르게 우선순위 큐를 하나만 썼습니다. 하나만 쓸 수 있었던게 가능했던 이유는 구간 집-사무실 사이의 구간 P(h, o)를 P를 포..

3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬로 풀기 5 5 4 3 2 1 2 2 4 3 4 처음 순위 [5,4,3,2,1]대로 단방향 그래프를 생성합니다. 5는 (4,3,2,1)보다 높으므로 5->4, 5->3, 5->2, 5->1 간선을 추가합니다. 4는 (3,2,1)보다 높으므로 4->3, 4->2, 4->1을 추가합니다. 3,2,1도 같은 방식으로 간선을 추가하면 5 -> [4,3,2,1] 4 -> [3,2,1] 3 -> [2.1] 2 -> [1] 1 -> [] 여기서 (2, 4)와 ..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 맨 처음 문제를 봤을 때, 얼음이 녹는다는 표현을 보고 예전에 풀었던 치즈가 생각나긴 했는데 치즈는 머리를 써야 푸는 문제였다면, 이 문제는 머리보다는 손을 더 많이 써야 하는 문제입니다. 각 칸의 얼음은 1년 마다 인접한 네 방향(동서남북) 중 바다(배열값이 0)인 갯수만 큼 녹아내려 0이되면 바다가 됩니다. 문제의 목표는 한 덩이의 얼음이 주어졌을 때, 두덩이 이상으로 변하기 까지의 시간을 구해야 합니다. 단, 동시에 전부 없어지면 0을 출력해야 합니다..

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 멀티탭을 바꿔 끼는 최소 횟수를 구하는 문제로 일단 문제 자체는 간단해 보입니다. 간단해 "보일" 뿐입니다. 접근 문제를 봐도 떠오르는 게 없습니다. 그럼 일단 쉬운 아이디어부터 생각해 봅니다. 브루트 포스 (Failed) 멀티탭에 다 찼을 시점 부터 새로운 물건을 꽂으려고 할 때 특정 위치에 꽂는 모든 경우를 구합니다. [2 3 1 2 7] 로 주어졌을 때 아래와 같은 방식으로 구하면 7로 도달했을 때 횟수가 2, 3이 되고 이 중 가장 작은 횟수는 2가..

2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제에 "의사전달시간" 이라는 말이 나옵니다. 지문에도 나와있지만 한 사람에서 다른 사람으로 의견을 전달할 때 거치는 사람의 수를 의미하며 여러 경로가 있으면 최단 거리를 "의사전달시간"으로 잡습니다. 당장 이것만 봐도 최단 거리를 구하기 때문에 다익스트라가 먼저 떠오릅니다. 그런데 문제는 위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하세요. 최댓값이 최소? 얼핏보면 헷갈릴 수도 있는 지문입니다. 즉 이걸 두줄..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 보드판에서 최대한 머무르는게 목표이므로 최소 비용이 아닌 최대 비용을 구하는 문제 입니다. 그리고 구멍에 빠지거나 보드판 밖으로 나가기 전 까지 머물러야 하기 때문에 최종 목적지가 상황에 따라 다릅니다. 최종 목적지가 상황에 따라 다르기 때문에 DFS 돌리되, 스택 보다는 재귀함수를 사용하는 것을 권장합니다. 그래야 (0,0) 위치에서 최장 거리를 구할 수 있으니까요. 무한 루프가 돌 수 있기 때문에 visited 배열을 사용해서 방문 여부를 체크합니다. 재귀 ..