기로에 서다

문제 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 1. 구해야 하는 것은 벌레가 [1, h] 높이를 지나갈 때, ① 부서지는 석순의 개수의 최소 값과 ② 그러한 개수를 만족하는 높이의 개수를 구해야 합니다. 2. ②번부터 생각해본다면, 높이를 지날 때마다 부서지는 석순의 개수를 인덱스로 갖고 그러한 높이들의 개수를 값으로 갖는 맵(stl)을 사용하면 첫 번째 원소 값 기준으로 오름차순 정렬된 채로 유지되기에 결과적으로 답은 맵의 첫 번째 원소의 인덱스(..

문제 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 i번째 비행기가 들어왔을 때 [1, g_i]게이트 중 어디에 도킹시킬지를 정해줘야 하는데 이는 아래와 같은 예를 떠올려보면 어렵지않게 큰 번호의 게이트부터 채워나가야함을 알 수 있습니다. ※ [1, 2, 3]의 게이트가 꽉 찼을 때, g = [5, 4]라면 1번째 비행기를 4번게이트에 두면 2번째 비행기가 도킹x, 반대로 5번게이트에 도킹하면 2번째 비행기가 도킹가능..

문제 www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 풀이 모든 전구의 상태를 완전탐색한다면 $O(2^n)$으로 시간초과가 나기 때문에 다른 방법을 생각해봐야 합니다. 문제에서 구하는건 최소한으로 누르는 스위치의 개수이기에 스위치를 누르는 횟수를 줄이기 위해서 같은 스위치를 2번이상 누르지 않도록 해야합니다. 1. 스위치를 누르는 방향을 정해놓고 전구를 순회하면 한 번 누른 스위치는 다시 누르는 경우가 생기지 않으므로 방향을 정해놓고 진행합니다. ..

문제 www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 현재 보고있는 지시사항에서 각 각의 발의 위치 상태에 따라 이동하는 비용이 전부 다르므로 상태를 정의하여 dp를 사용하면 해결할 수 있습니다. 1. "dp[cmd_idx][left][right] : 현재 보고 있는 지시사항의 인덱스(cmd_idx)에서 왼발의 위치가 left, 오른발의 위치가 right일 때, 모든 지시 사항을 만족하는 데 사용되는 최소의 힘"이라고 ..

문제 www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 연속된 세 집의 색깔을 결정하는게 아니라 연속된 두 집의 색을 결정해간다고 생각하면 다른 집들과 조건이 다른 첫 집의 색을 고정했을 때, 나머지 집의 가능한 색을 찾아 비용을 최소화하는 방법으로 생각할 수 있습니다. 2. "dp[cur][precolor] = 현재 cur번째 집의 색을 결정하고 있으며, 바로 전 집을 precolor로 칠했을 때 모든 집을 칠하는 최소..

문제 www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 풀이 1. 모든 합성수는 소인수분해를 통해 소수의 곱으로 표현할 수 있고, 그 개수들을 카운트하기 위해 소수들의 개수를 담는 배열을 사용합니다. 또한 정수, 유리수 판별에 음수 여부는 관계없으므로 편의를 위해 모두 양수로 바꿔줍니다. 2. 곱하는 수는 소인수 분해하여 표현된 소수들의 개수를 올려주고, 나누는 수는 소인수 분해하여 표현된 소수들의 개수를 빼주어 그 개수들을 관리할 수 있습니다. (곱하는 수 중 0이 존재한다면 항상 결과는 0이므로 이는 따로 처리해줍니다.) 3..

문제 www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net 풀이 기존의 요세푸스 문제는 항상 원소가 제거되는 방향이 앞에서 뒤로 일정하여 큐를 사용할 수 있었지만, 이 문제에선 반대 방향도 존재하기때문에 편의를 위해 덱을 사용하여 해결할 수 있습니다. (물론 큐를 사용하여 방향이 바뀔 때마다 큐를 역순으로 바꿔서 해결할 수도 있습니다.) 1. 방향과 상관없이 앞에서 뒤(뒤에서 앞)으로 k번째 사람을 제거하므로 k - 1번 사람을 뒤로 넘기거나 앞으로 넘겨주고 k번 사람을 제거합니다. 2. 그렇게 제거한 사람의 수..

문제 www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 풀이 구해야 하는 건 기구를 두 개씩 사용해서 일어나는 근손실의 합의 최대를 M이라 할 때, 이를 최소화해야 합니다. "최대의 최소화" 꼴이라 이분 탐색도 가능하지만 그보다 간단하게 근손실의 정도를 오름차순으로 정렬하고, 매칭 되지 않은 오른쪽 끝 값(최대 값)을 왼쪽 끝 값(최소 값)과 매칭시켜주는 방법을 통해 해결할 수 있습니다. (n이 홀 수일 경우에 한 번은 1개의 기구만 선택해야 하므로 이는 최대 값을 선택한 후, ..

문제 www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 풀이 STL map을 사용하면 문자열인 확장자들의 개수를 관리할 수 있고, 출력할 때는 맵을 순회하면서 확장자명과 개수를 출력하여 간단하게 해결할 수 있었습니다. 코드 #include using namespace std; int n; string s; map mp; int main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin >..

문제 www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/probl..