Devlog

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

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 정수 N이 있습니다. i자리의 수와 j자리의 수를 서로 바꾸는 작업을 K번 반복해서 나온 수들 중, 최댓값을 구하는 문제 입니다. DP+브루트포스로 푸는 방법과 그래프 탐색으로 푸는 방법이 존재하지만 원리는 거기서 거기이기 때문에 여기선 그래프 탐색으로 푸는 방법만 설명하려고 합니다. 사실 N, K범위가 작기 때문에 브루트포스 방법이 먹혔던 거지 범위가 길었으면 시간초과가 발생 할 풀이 입니다. 그리디가 아닌 이유 얼핏 보면 그리디 처럼 보입니다. 수들을 이리저리 움직여서 수의 최대값을 맞추는 문제 처럼 보이기 때문입니다. K번 이..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 위와 같은 3x3 퍼즐이 있을 때 퍼즐위의 숫자들을 오름차순으로 정렬할 수 있는 최소 이동 횟수를 구하는 문제입니다. 얼핏보면 그냥 평범한 백트래킹 혹은 BFS 문제처럼 보이지만 메모리 제한(25MB)이 걸려있습니다. 접근 일반적인 BFS를 이용한 최소 비용을 구하는 문제들은 visited라는 방분 여부 변수를 사용하는데 이 문제에서는 visitied 배열을 9차원 배열로 선언해야 합니다. (ex: visited[0][1][2][3][4][5][6][7][8]) 그렇게 되면 visited의 크기는 9^9가 되는데 이 길이는 억단위를 ..