기로에 서다

문제 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..

문제 www.acmicpc.net/problem/20167 20167번: 꿈틀꿈틀 호석 애벌레 - 기능성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 20167 풀이 N의 상한이 20이기에 i번째 먹이를 먹었거나 안 ..

문제 www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 풀이 1. 문제에서 친절하게 찾고자하는 문자열이 중복되는 경우가 존재할 수 있다고 했으므로 맵을 사용해서 한 번 계산한 문자열은 다시 계산하지 않을 수 있습니다. 2. 문자열을 찾는 쿼리마다 n * m 격자를 순회하는데 이 때 아래와 같이 맵밖으로 나가는 경우만 따로 처리해주면 "현재 좌표에서부터 찾을 수있는 문자열의 개수"를 반환하는 함수를 작성해 해결할 수 있습니다. 코드 #include using namespace std; const int dir[8][2] = { {-1,0},{1,..

문제 www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 풀이 문제에서 주어진 진행방식을 읽고, 아래를 생각하면서 구현하면 어렵지 않게 구현할 수 있습니다. 1. 한 도미노가 엎어질 때, 서있는 다른 도미노가 같은 방식으로 엎어지므로 "엎어진 도미노의 개수를 반환"하는 함수를 작성해 쓰러진 도미노의 개수를 셀 수 있습니다. 2. 길이가 K인 도미노가 넘어져 K - 1개의 도미노가 쓰러질 때, 이미 쓰러져있는 도미노는 영향을 받지 않습니다. 따라서 ..

문제 www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 풀이 문제의 연산을 살펴보면 숫자를 세 개의 숫자로 분할하거나, 숫자의 자릿수들을 검사하므로 편의를 위해 다루는 숫자들을 문자열로 처리하기로 하며, 이 문제의 시작이자 끝인 분할하는 함수를 생각해봅시다. 1. 숫자를 분할하고 새로운 숫자를 만들어내는 연산을 한 후, 새로운 숫자도 연산을 거쳐야 하므로 분할하는 과정은 재귀를 사용해 해결해야 함을 알 수 있습니다. 2. 아래의 그림과 같이 길이가 k$(k>=..

문제 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 1. 어떤 칸에 빗물이 채워지는 조건에 대해서 생각해볼 때, 그 칸을 제외한 (좌측의 최대 높이, 우측의 최대 높이) 둘 중 작은 높이에서 어떤 칸의 높이를 뺀 만큼 채워진다는 걸 알 수 있습니다. (물론 물이 채워져야 하므로 좌측의 최대 높이, 우측의 최대 높이는 어떤 칸의 높이보다 높아야 합니다.) 2. i칸을 제외한 i칸 좌측의 최대 높이를 $pre[i]$, 우측의 최대높이를 ..

문제 programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 1. 이동하는 비용에 대해서 살펴보면 다음 칸으로 이동할 때의 방향이 현재 칸으로 이동한 ..

문제 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 1. 어떤 조건(모든 보석종류를 포함)을 만족하고 연속되는 가장 짧은 구간을 찾는데 N의 상한이 10^5이기에 투포인터로 푸는문제임을 알 수 있습니다. 2. 보석의 이름을 매핑하며 모든 보석의 종류의 개수를 세어줍니다. 3. "[l, r)구간의 보석의 종류(Curkind)가 모든 보석의 종류(Allkind)를 포함하는가?" 라는 조건을 기준으로 l, r을 움직이는데 현재 보는 보석의 개수(gemscnt)를 관리해가..