백준 17141 - 연구소2 시간 제한 1초, 메모리 제한 512MB # 조건 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다..

백준 15970 - 화살표 그리기 시간 제한 2초, 메모리 제한 512MB # 조건 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. 에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다. 각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다. 각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운..

시간 제한 1초, 메모리 제한 1024MB # 조건 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 $E$에서 $S$로 올 때 $S$에서 $E$로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 $S$에서 $E$로 가는 가장 짧은 거리와 $E$에서 $S$로 가는 가장 짧은 거리를 원한다. 정점 $S$에서 정점 $E$로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 $S$에서 정점 $E$로 이동한 경로를 나열했을..

백준 16927 - 배열 돌리기2 시간 제한 1초, 메모리 제한 512MB # 조건 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5] 예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다. 1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2 7 8 2 ..

백준 14675 - 단절점과 단절선 시간 제한 1초, 메모리 제한 512MB # 조건 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다. 이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다. 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프 트리의 정보와 질의가 주어질 때, 질의에 대한 답..

백준 2018 - 수들의 합 5 시간 제한 2초, 메모리 제한 32MB # 조건 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 입력 첫줄에 정수 N이 주어진다. 출력 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오. # 접근 방법 투 포인터를..

백준 2847 - 게임을 만든 동준이 시간 제한 1초, 메모리 제한 128MB # 조건 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다. 이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다. 각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구..

백준 18223 - 민준이와 마산 그리고 건우 시간 제한 1초, 메모리 제한 256MB # 조건 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다. 지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다. 정점은 1~V까지 있다. 건우는 P번 정점에 있다. 그리고 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다. 중복되는 간선..

백준 5766 - 할아버지는 유명해! 시간 제한 1초, 메모리 제한 256MB # 조건 IBA(국제 브릿지 협회)는 수 년간, 매주 가장 실력있는 선수들의 랭킹 정보를 기록해왔습니다. 매주 랭킹에 선수의 이름이 오를 때마다 선수의 포인트가 1포인트씩 오르는데, 할아버지께서 가장 많은 포인트를 얻어서 최고의 브릿지 선수로 선정되었습니다. 할아버지께는 그와 브릿지 순위를 경쟁하는 친구들이 많이 있었기 때문에, 할아버지는 어떤 선수(들)가 2등을 했는지 정말 궁금하셨습니다. IBA 랭킹 정보는 이제 온라인에 올라와 있고, 할아버지께서 당신에게 도움을 요청했습니다. 당신은 매주마다의 랭킹 정보 리스트를 인풋으로 받아 2등 선수가 누구인지 알아내는 프로그램을 짜야 합니다. 입력 각 선수는 1~10000까지의 정수..