3주차 | 문제 4. 순환하는 수로 문제 구름이는 도시의 물을 관리하는 관리자이다. 현재 도시에는 물을 잠시 보관하는 물탱크와 물탱크끼리 연결하는 수로가 아래의 조건으로 설치되어 있다. N개의 물탱크와 N개의 수로가 있다. 물탱크는 1번부터 N번까지 있다. 수로가 연결된 물탱크는 양 쪽으로 물이 흐른다. 서로 다른 두 물탱크를 잇는 수로는 최대 하나이다. 물탱크에서 연결된 물탱크는 항상 다른 물탱크이다. 도시의 물은 흐르지 않으면 녹조류가 생기기 때문에, 항상 물이 순환하도록 유지하는 것이 중요하다. 하지만, 구름이는 순환하는 물이 항상 모든 물탱크를 지나지 않는다는 점을 확인했다. 구름이는 현재 상태의 수로를 확인하고, 순환하는 수로를 찾기로 한다. 이때 순환하는 수로란, 물탱크의 물이 아래의 조건을 ..

3주차 | 문제 3. 구름이의 여행 문제 구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있습니다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했습니다. 설치된 다리들은 아래의 특징들을 만족합니다. 모든 다리는 양방향으로 이동할 수 있습니다. 서로 다른 두 섬을 잇는 다리는 최대 하나입니다. 다리가 잇는 두 섬은 항상 다른 섬입니다. 구름이는 1번 섬에서 출발해서 N번 섬으로 가려고 하는데, 통과하는 다리의 개수가 K개 이하가 되길 원합니다. 구름이를 도와 1번 섬에서 N번 섬까지 K개 이하의 다리만을 이용해 도착할 수 있는지를 구해봅시다. 예시 첫 번째 예시를 그래프로 나타내보면 아래 그림과 같습니다. 다리의 배치가 위..

3주차 | 문제 2. 폴더폰 자판 문제 10년 전, 구름이가 처음으로 구매했던 휴대폰은 폴더 폰이다. 폴더 폰의 자판은 최근의 휴대폰의 입력 방식과는 차이가 있다. 폴더 폰의 자판 형식은 아래와 같다. 9개의 입력 버튼으로 이루어져 있으며, 각 버튼의 첫 번째 숫자로 버튼을 부를 수 있다. 한 번 버튼을 누르면 숫자가 입력이 되고, 여러 번 누르면 자판에 보이는 문자들로 순서대로 바뀐다. 예를 들면 [버튼 5]를 한 번 누르면 5가 입력이 되지만, [버튼 5]를 세 번 누르면 k가 입력된다. 또 [버튼 5]를 5번 이상 누르게 되면 다시 처음 숫자가 입력된다. [버튼 7] 이나 [버튼 1]은 6번 이상일 때 동일하게 된다. 10년 전 구름이가 구매한 폴더 폰을 오랜만에 꺼내서 작동을 했더니, 휴대폰이 고..

3주차 | 문제 1. 0커플 문제 구름이는 다가오는 크리스마스에 커플이 아닌 지인들을 서로 소개해 주기로 한다. 구름이는 최대한 많은 커플들이 생기기 바라는 마음으로 아래의 기준으로 지인들에게 점수를 부여한다. 구름이의 지인의 수는 항상 짝수이다. 모든 점수는 0점을 제외한 정수이다. 지인들 중 같은 점수를 가지고 있는 경우는 없다. 만약에 n점이 있다면 -n이 항상 존재한다. 구름이는 지인들 중 점수의 합한 값이 0이 되는 두 명을 짝지어서 소개팅을 진행하기로 한다. 구름이는 위와 같은 규칙으로 지인의 점수를 부여하다가 실수로, 4번째 규칙을 지키지 못했다. 그래서 두 사람이 소개팅을 받지 못하게 되었다. 구름이가 이 문제를 해결하기 위해서 소개팅을 진행하지 못한 두 사람의 점수를 합한 값을 출력하시오..

2주차 | 문제 4. 폭탄 구현하기 문제 아래와 같은 그림의 정사각형이 있다. 그림과 같이 정사각형을 동일한 크기의 칸으로 나누었다고 했을 때, 맨 오른쪽, 아래의 칸을 arr[n][n]이라고 표현한다. 모든 위치에는 폭탄 값이 있는데, 모든 폭탄 값의 초기 값은 0이다. 위 그림을 기준으로 나누어진 사각형 중 하나를 선택하여 폭탄을 떨어트립니다. 폭탄이 떨어진 지점은 arr[2][3]이라고 하면 아래의 노란색 모양으로 폭탄이 터진다. 위의 십자가 모양처럼 폭탄이 터지면 폭탄이 터져 영향을 받은 위치의 폭탄 값이 올라갑니다. 이를 그림으로 표현하면 아래와 같습니다. 이때 폭탄 값은 영향을 받는 횟수만큼 무한히 올라간다. 즉 같은 위치에 여러 번 영향을 받는다면, 그 만큼 폭탄 값이 증가한다. 폭탄이 터지..

2주차 | 문제 3. 출석부 문제 구름이는 N명의 사람들의 이름과 키 정보를 가지고 있는 출석부를 만들기로 합니다. 출석부의 순서는 이름을 기준으로 사전 순서로 정렬되어 있지만, 이름이 같다면 키가 큰 순서대로 정렬하기로 합니다. 이때, 사람들의 이름과 키가 모두 같은 사람은 없으며, 키는 소수 2번째 자리 까지 알고 있습니다.모든 사람들의 이름과 키가 주어졌을 때, 출석부를 완성하고 k번째 있는 사람의 이름과 키를 공백을 두고 출력하시오. 입력 첫째 줄에 사람의 수 N(1≤N≤10,000)과 찾아야 하는 수 k(1≤k≤N)이 공백을 두고 주어진다. 둘째 줄부터 N줄에 걸쳐서 사람의 정보가 주어진다. 사람의 정보는 이름 s와 키 t가 각각 공백을 두고 주어진다. 이름은 모두 알파벳 소문자이며, 키는 10..