코딩테스트

문제 읽기🤔 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지..

문제 읽기🤔 문제 선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다. 각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다. 입력 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj..

문제 읽기🤔 문제 개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네. 개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네. 한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들! 우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다. 행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다. 로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다. 이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다. 로봇 개미 ..

문제 읽기🤔 문제 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다. 오두막들은 1번부터 N번까지 번호가 붙어 있으며, 1번 오두막이 산 정상에 있다. 1번 오두막에서 다른 오두막으로 가는 가장 짧은 길을 따라 가면서 거치는 모든 오솔길들은 항상 산을 내려가는 방향이다. 철수는 등산 마니아이다. 철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거치는 가장 짧은 길을 따라 간다. 이렇게 간 길의 다양성은 길에 포함된 오솔길의 개수로 정의된다. 두 번 이상 지나간 오솔길은..

문제 읽기🤔 문제가 너무 길어서 요약으로 대체합니다 :) 위와 같이 모노미노도미노 게임을 위한 보드가 주어진다. 모노미노도미노 게임에서 사용되는 블록은 다음과 같다. 빨간 보드에 블럭을 놓으면 해당 위치 기준으로 더 이상 움직일 수 없을 때까지 행/열을 따라 이동한다. 블럭이 사라지는 경우 1) (초록)행//(파랑)열이 모두 블럭으로 채워진 경우 -> 해당 줄의 블럭은 모두 사라짐, 해당 줄의 앞줄에 존재하는 블럭들은 사라진 행/열의 개수만큼 행/열을 따라 뒤로 이동 -> 1점을 얻는다. 2) 희미한 부분에 블럭이 채워진 경우 -> 희미한 부분에 블럭이 있는 (초록)행/(파랑)열의 수만큼 맨 뒷 행/열에 있는 타일들이 사라짐 -> 해당 줄의 앞줄에 존재하는 블럭들은 사라진 행/열의 개수만큼 행/열을 따라..

문제 읽기 🤔 문제 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다. N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가..

문제 읽기🤔 문제 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다. 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다. 욱제의 ..

정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘 동작 그리디 + 동적 계획법 방문하지 않은 노드 중에서 가장 비용이 작은 노드를 선택(Greedy) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신(DP) 초기의 Dijkstra 알고리즘 거리 테이블을 매번 탐색하는 순차 탐색 방식 최악의 경우 모든 노드들을 확인해야 함 → 이것을 V번 반복 시간복잡도 $$O(V^2)$$ 방문 여부를 체크할 배열 각 노드까지의 최소 비용을 저장할 배열 미 방문한 노드는 무한한 값으로 초기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..