Devlog

20136번: 멀티탭 스케줄링 2 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 지금 포스트를 작성하는 시점으로부터 약 1달 전에 멀티탭 스케줄링 1탄을 리뷰한 적이 있었습니다. [백준 1700] 멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면 storyofvector7.tistory.com 문제 내용은 같지만 멀티탭 스케줄링 2탄에서는 비현실적인 멀티탭을 다룹니다. 무려 멀티..

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 문제에 "의사전달시간" 이라는 말이 나옵니다. 지문에도 나와있지만 한 사람에서 다른 사람으로 의견을 전달할 때 거치는 사람의 수를 의미하며 여러 경로가 있으면 최단 거리를 "의사전달시간"으로 잡습니다. 당장 이것만 봐도 최단 거리를 구하기 때문에 다익스트라가 먼저 떠오릅니다. 그런데 문제는 위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하세요. 최댓값이 최소? 얼핏보면 헷갈릴 수도 있는 지문입니다. 즉 이걸 두줄..