🔗문제 보러가기 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 🧑‍💻풀이 과정 BFS로 쉽게 풀 수 있는 문제인데, 저는 사다리나 뱀을 타고 간 보드칸을 방문 처리해주질 않아, 엉뚱한 답이 나왔습니다. 이걸 빨리 알아채지 못해서 시간을 좀 허비했네요. 아무튼, 제가 푼 풀이 과정은 다음과 같습니다. 뱀이나 사다리 정보를 가지고 있는 vector teleports(100 + 1)을 준비한다. teleports[i] = 0 👉🏻 뱀이나 사다리가 없음을 의미 telep..

🔗문제 보러가기 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🧑‍💻풀이 과정 string을 스택(stack)처럼 사용하여 풀었습니다. 정답을 저장할 string 변수(answer)를 따로 준비한 후, 주어진 문자열을 차례대로 순회하였습니다. 그리고 다음과 같은 과정을 진행해 주었습니다. 현재 읽은 문자열을 answer 변수에 넣습니다. 현재 읽은 문자열이 폭발 문자열의 마지막 문자와 같다면, 다음 과정을 거칩니다. answer와 폭발 문자열을 뒤에서부터 차례대로 읽으며 비교합니다. 두 문자열..

🔗문제 보러가기 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🧑‍💻풀이 과정 등간격으로 설치할 수 있는 가장 큰 간격을 매개변수 탐색으로 구하면 됩니다. 입력 받은 집 위치들을 배열(arr)에 담고, 오름차순으로 정렬해준 뒤에 다음 과정을 진행해 주었습니다. left = 0 (첫 번째 ~ 첫 번째 공유기 사이의 범위), right = arr[N - 1] (첫 번째 ~ 마지막 공유기 사이의 범위) mid = (left + right) / 2로 중간 범위값을..

🔗문제 보러가기 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🧑‍💻풀이 과정 매개변수 탐색으로 풀 수 있습니다. 저는 다음과 같이 풀었습니다. 입력 받은 예산들을 오름차순으로 정렬합니다. 예산들의 합계가 M 이하라면, 예산들 중 최댓값(배열의 마지막 값)을 출력하고 종료합니다. 그게 아니라면, 최소 예산값(1)과 최대 예산값(배열의 마지막 값)을 가지고 이분 탐색을 시작합니다. "mid = (left + right) / 2" 값을 계산합니다. 예산의 총 합계를 계산하되, mid 값보다 큰 예산은 mi..

🔗문제 보러가기 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🧑‍💻풀이 과정 N이 최대 \( 10^5 \)라서, 당연히 \( \mathrm{O(n^2)}\) 알고리즘은 바로 컷 당합니다. 그렇다면, A[i][j] = \( i \times j \)으로 구성되는 2차원 배열은 만들 수가 없다는 얘기가 되는데 어떻게 풀어야 할 지 막막했습니다. 결국 다른 분들의 힌트를 찾아서 살펴 봤네요. 세상엔 정말 똑똑한 사람들이 많은 것 같습니다. 어떻게 이런 생각을 해낼까란 감탄이 나올 정..

🔗문제 보러가기 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 🧑🏻‍💻풀이 과정 다리를 건너기 위해 대기 중인 트럭들, 다리를 건너는 중인 트럭들을 관리할 2개의 큐(Queue)를 선언합니다. 해당 2개의 큐가 모두 비었다면, 반복문을 종료합니다. 아니라면, 다리를 건너는 트럭들 중 맨 앞 트럭이 다리를 건넜는지 확인합니다. "경과시간 - 해당 트럭이 다리에 진입한 시각 = 다리의 길이"라면, 다리를 건넜습니다. 이 경우, 총 무게에서 해당 트럭 무게를 빼주고,..