https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 이 문제는 문제를 읽기 조차 조금 힘들다.. 간단히 설명부터 하자면, 1 3 6 6 7 9가 있을 때 기지국이 2개라고 주어진다면 기지국 1이 [1~3]을 수신하고 기지국2가 [6~9]를 수신할 때 수신가능영역이 최소가 된다! 이제 이 문제를 푸는 방법에 대해 알아보자. 우선 입력으로 주어진 값을 정렬해주자. 1 6 9 3 6 7 이라는 예제가 주어졌다고 하면 이를 정..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전1과 유사한 DP문제이다. DP는 점화식을 세우는 것이 중요한데, 이 점화식을 찾기 위해 문제의 예제를 이용해보자. i원을 만들기 위해서 필요한 동전의 수를 dp배열에 저장할 것이다. 0원을 만들기 위해서는 동전 0개가 필요하다 -> dp[0]=0; 1원을 만들기 위해서는 1원짜리 동전 1개가 필요하다 -> dp[1]=1; 2원을 만들기 위해서는 2원짜리 동전 2..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 영역 구하기 2. 영역 중에서 바다와 맞닿은 (= 제일 끝쪽에 있는) 곳들 찾아주는 함수 작성 3. 사이드 영역에서 다른 영역까지의 최단거리 구하기 이 문제의 해결법은 크게 위 3단계로 나눌 수 있다. 1번 해결법 설명 : dist배열을 활용하여 모든 육지가 아닌, 아직 탐색하지 않은 영역인 경우에만 탐색을 진행한다. cnt 변수를 이용하여 번호를 매겨주면 된다! 2번 해결법 설명 : 바다와 맞닿..
https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 가장 공평한 곳에 우체국을 설치한다..! 라고 문제를 이해한다면 풀이법에 접근하기 훨씬 간단해진다. 보통 친구들과 약속 장소를 정할 때, 중간 지점일 수록 그리고 친구의 수가 많은 곳일 수록! 위 2가지로 정할 것이다. 우리는 이러한 룰을 문제에 적용시켜볼 것이다. 먼저 마을 번호를 기준으로 오름차순 정렬한다. ..
https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 간단한 문자열 탐색 문제이다. 첫번째 문자열을 전부 탐색하면서, 매번 두번째 문자열이랑 비교해준다. 현재 i번째 인덱스에서부터 비교를 해줘야하기 때문에, i+j인덱스와 j인덱스를 비교해주는 것! 비교했는데 동일하지않다면 for문에 의해 i가 1증가하면서 다시 탐색을 해주고, 만약 동일하다면, 예를 들어 3글자짜리와 비교했을 때 단순히 i가 1만 증가하면 중복되어 세는 경우가 발생할 수 있으므로 i를..
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 이 문제 상당히 까다로운데, 풀이법은 다음과 같다. 1. 중복된 것이 꽂혀있다면 아무것도 하지 않는다. 2. 아무것도 안 꽂혀있다면 하나 꽂아준다. 3. 바꿔야할 전자기기의 다음 순서부터 탐색을 하는데, 멀티탭에 꽂혀있는 것들 중에서 가장 나중에 다시 등장하는 기기를 뽑아주면 된다! 1, 2번은 코드 이해에 크게 무리가 없으리라 생각하고 3번에 대해서만 자세히 설명하도록 하겠다. cnt++..