💡문제 [Gold V] 개똥벌레 - 3020 문제 링크 성능 요약 메모리: 29804 KB, 시간: 252 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 $O(\sqrt {NH}$ 또는 $O(N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 H개의 높이에 대해서 N개의 장애물에 대해 탐색하며 몇개의 장애물을 통과해야할지 판별→ $O(NH)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(NH)$ 당연히 시간복잡도 초과 ❌ 접근 방법. 완탐 높이 H를 인덱스로 가지는 배열을 생성 장애물을 차례대로 탐색하며 높이에 장애물이 존재하는 높이에 업데이트 → $O(NH)$ 길이가 2인 석순이라면 높이 1에 +1, 높이 2에 +1 길..

💡문제 [Gold III] 두 배열의 합 - 2143 문제 링크 성능 요약 메모리: 112696 KB, 시간: 556 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 -1,000,000,000 ≤ T ≤ 1,000,000,000 (십억) 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수 $O(\sqrt T)$ 또는 $O(n^2)$이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 배열 A의 가능한 부분 배열 만들기 → $O(N^2)$ 배열 B의 부분합이 T-(배열 A의 부분합)인 모든 부 배열 찾기 → $O(N^2)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N^4)$ 당연히 시간복잡도 초과 ⭕ 접근 방법. Map을 이용해 누..

[Silver II] 수들의 합 4 - 2015 문제 링크 성능 요약 메모리: 35852 KB, 시간: 312 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ N ≤ 200,000 |K| ≤ 2,000,000,000 (20억) $O(N\sqrt N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 시작점이 0 ~ N-1 , 끝점이 0 ~ N-1로 두고 가능한 모든 부분 배열을 지정한다. → $O(N^2)$ 부분 배열을 순회하며 부분합을 구한다. → $O(N)$ 부분합이 k와 같은지 비교한다. ➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$ 시간복잡도가 너무 커서 시간이 부족하다. ❌ 접근 방법. 누적합 누적합 배열($S_n)$을 만든다. → $O(N)$ $S_b-S_{..

## 💡문제 ### [Silver II] 조합 0의 개수 - 2004 [문제 링크](https://www.acmicpc.net/problem/2004) #### 성능 요약 메모리: 11564 KB, 시간: 76 ms --- #### [깨진 부분은 여기에서 확인](https://velog.io/@dksek3050/%EB%B0%B1%EC%A4%80-Java-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98%EC%A0%95%EC%88%98%EB%A1%A0) ## 🤔접근법 ### 범위 체크 및 시간복잡도 예상 - 0 ≤ m ≤ n ≤ 2,000,000,000 (20억) n ≠ 0 - $O(\sqrt N)$ 또는 $O(logN)$ 이어야 한다. ###..

💡문제 [Gold V] 실질적 약수 - 2247 문제 링크 성능 요약 메모리: 11588 KB, 시간: 732 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ n ≤ 200,000,000 .. 2억 시간 제한이 2초라 $O(N)$ 도 가능할 거 같다. 풀이법 ❌ 첫번째 접근 방법 . 에라토스테네스의 체 소수 판별 (에라토스테네스의 체) $O(log(logN))$ 소수가 아닌 N에 대해 순회 $O(N)$ → (여기가 이미 188,921,062) 실질적 약수 구하기 SCD(N) $O(\sqrt N)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N\sqrt N)$이다 ⭕ 두번째 접근 방법 . N까지 x의 배수의 개수 1 ~ N까지 순회 $O(N)$ N 이하의 수에서 어떤 수 i를 ..

💡문제 [Gold V] 등차수열과 쿼리 - 23888 문제 링크 성능 요약 메모리: 324788 KB, 시간: 1360 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ $a$ ≤ $10^6$, 0 ≤ $d$ ≤ $10^6$ 1 ≤ $q$ ≤ $10^6$ 1 ≤ $l$ ≤ $r$ ≤ $10^6$ 완탐은 힘들듯 하다. $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 1 $l$ $r$ : $l$ 번째 항부터 $r$ 번째 항까지의 합 → 등차수열 합공식 등차 수열의 합공식을 이용하면 상수 시간으로 구할 수 있을 것이라고 생각했다. 등차수열 합공식 : 항의 개수 * (첫째항 + 끝항) / 2 항의 개수가 n개인 등차 수열의 첫째항을 a, 끝항을 $l$ , 공..

💡문제 [Silver III] 소수의 자격 - 6219 문제 링크 성능 요약 메모리: 16376 KB, 시간: 148 ms 🤔접근법 범위 체크 및 시간복잡도 예상 범위 : 1 ≤ A ≤ B ≤ 4,000,000 , B ≤ A + 2,000,000 범위 순회 * 소수 판정 $O(N^2)$은 최대 범위가 2백만이라 어렵다. $O(N\sqrt N)$도 1,000,000 * 1000 이라 어렵다 . $O(Nlog{N})$ 은 될 지 잘 모르겠다. 가능할듯 (대충 N * 8 정도 예상…) $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 🅰️ 첫 번째 접근방법. 완탐 ⭕ 범위 A ~ B 까지 순회하면서 각 숫자들이 소수인지 판별 소수이면 D를 포함하는지 판별 ➡️ 해당 풀이법의 시간 복잡도..

💡문제 [Gold IV] 2로 몇 번 나누어질까 - 1407 문제 링크 성능 요약 메모리: 11552 KB, 시간: 76 ms 🌟풀이 범위가 무려 1≤A≤B≤$10^{15}$ 로 엄청나다. 그래서 A ~ B 까지 순회하면서 더할 수는 없다. 1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다. 1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ? 1부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다. 이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다. 위를 참고하여 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 ..

[Platinum V] 숨바꼭질 5 - 17071 문제 링크 성능 요약 메모리: 89244 KB, 시간: 248 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위..

[Gold I] 열쇠 - 9328 문제 링크 성능 요약 메모리: 320872 KB, 시간: 1328 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 문제 설명 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너..

[Gold III] 줄 세우기 - 2252 문제 링크 성능 요약 메모리: 46084 KB, 시간: 4360 ms 분류 그래프 이론, 위상 정렬 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 ..

[Silver V] 수 정렬하기 2 - 2751 문제 링크 성능 요약 메모리: 134424 KB, 시간: 692 ms 분류 정렬 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 💡 나의 접근 주어진 N의 개수가 1,000,000이기 때문에 O(N^2) 시간복잡도를 가지게 되면 터지게 된다. 그래서 O(NlogN)이나 O(N) 시간복잡도를 가지는 정렬을 생각해 보아야 할 것이다. A..

[Silver III] 계단 오르기 - 2579 문제 링크 성능 요약 메모리: 11608 KB, 시간: 76 ms 분류 다이나믹 프로그래밍 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 ..

[Bronze I] 비밀편지 - 2596 문제 링크 성능 요약 메모리: 11476 KB, 시간: 72 ms 분류 구현, 문자열 문제 설명 병현이는 지은이에게 문자 A, B, C, D, E, F, G, H 로 쓰여진 편지를 날마다 보내는데, 컴퓨터로 보내는 비밀편지로, 한 문자마다 0 또는 1인 숫자 여섯 개를 사용하여 보낸다. 둘 사이의 약속은 다음과 같다. A 000000 B 001111 C 010011 D 011100 E 100110 F 101001 G 110101 H 111010 병현이가 어느 날 001111000000011100 을 보내면 지은이는 이것을 BAD로 이해하게 된다. 그런데 둘 사이에 약속이 잘 만들어져 있기 때문에, 통신에 문제가 생겨서 한 문자를 표시하는 여섯 숫자 중 어느 한 숫..

[Silver I] 주지수 - 15724 문제 링크 성능 요약 메모리: 121296 KB, 시간: 648 ms 분류 다이나믹 프로그래밍, 누적 합 문제 설명 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 는 1 ..

[Silver III] 안테나 - 18310 문제 링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 프리뷰 답을 도출하는 데 살짜쿵 버벅했지만 막상 코드를 짜고보니 너무너무 간단해서 이게 맞나 싶었다... 돌려보니 이게 돌아가서 당황했다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 성능 요약 메모리: 40748 KB, 시간: 348 ms 분류 그리디 알고리즘, 수학, 정렬 문제 설명 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의..

[Silver I] 트럭 - 13335 문제 링크 성능 요약 메모리: 12844 KB, 시간: 96 ms 분류 자료 구조, 구현, 큐, 시뮬레이션 문제 설명 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의..

[Silver II] 화학식량 - 2257 문제 링크 성능 요약 메모리: 11516 KB, 시간: 80 ms 분류 자료 구조, 스택, 문자열 문제 설명 우리가 널리 사용하는 H2O(물), CH3COOH(아세트산)과 같은 화학식은 알파벳과 숫자, 그리고 괄호로 구성된다. 먼저 알파벳은 원자를 나타내는 것으로 H는 수소(Hydrogen), C는 탄소(Carbon), O는 산소(Oxygen) 원자를 뜻한다. 또한 원자를 나타내는 알파벳 뒤에 따르는 숫자는 그 원자가 몇 개 포함되어 있는지를 뜻한다. 따라서 COOHHH 분자는 CO2H3로 나타낼 수 있다. 이 문제에서, 숫자는 항상 2 이상 9 이하로만 입력으로 주어진다. 따라서 CO23과 같이 숫자가 두자리인 경우는 없다. 물의 화학식을 보고 물은 두 개의 ..

[Silver II] DNA 비밀번호 - 12891 문제 링크 성능 요약 메모리: 34668 KB, 시간: 208 ms 분류 슬라이딩 윈도우, 문자열 문제 설명 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에..

[Silver II] 꽃길 - 14620 문제 링크 성능 요약 메모리: 15968 KB, 시간: 132 ms 분류 브루트포스 알고리즘 문제 설명 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다. 꽃을 심을 때는 주..

[Silver II] 친구 - 1058 문제 링크 성능 요약 메모리: 11984 KB, 시간: 84 ms 분류 브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색 문제 설명 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. 입력 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 ..

[Silver II] 에디터 - 1406 문제 링크 성능 요약 메모리: 85980 KB, 시간: 468 ms 분류 자료 구조, 연결 리스트, 스택 문제 설명 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨..

[Silver III] 반전 요세푸스 - 20301 문제 링크 성능 요약 메모리: 19772 KB, 시간: 308 ms 분류 자료 구조, 덱, 구현, 시뮬레이션 문제 설명 요세푸스 문제는 다음과 같다. 1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K(≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까? 이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다. 하지만 한..

[Silver IV] 요세푸스 문제 - 1158 문제 링크 성능 요약 메모리: 15204 KB, 시간: 136 ms 분류 자료 구조, 구현, 큐 문제 설명 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어..

[Silver III] 십자카드 문제 - 2659 문제 링크 성능 요약 메모리: 15096 KB, 시간: 100 ms 분류 브루트포스 알고리즘, 구현, 정렬 문제 설명 위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다. 모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다. 입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가..

[Silver III] 킹 - 1063 문제 링크 성능 요약 메모리: 11596 KB, 시간: 80 ms 분류 구현, 시뮬레이션 문제 설명 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다. 킹은 다음과 같이 움직일 수 있다. R : 한 칸 오른쪽으로 L : 한 칸 왼쪽으로 B : 한 칸 아래로 T : 한 칸 위로 RT : 오른쪽 위 대각선으로 LT : 왼쪽 위 대각선으로 RB ..

[Silver III] 수리공 항승 - 1449 문제 링크 성능 요약 메모리: 11612 KB, 시간: 80 ms 분류 그리디 알고리즘, 정렬 문제 설명 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하..