기로에 서다

문제 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]$, 우측의 최대높이를 ..

문제 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 풀이 간단한 구현 문제이지만 신경 써야 할 부분이 몇 가지가 있었습니다. 1. 로봇이 내리는 경우는 벨트가 한 칸 회전해서 N번칸에 도착하거나 N-1번 칸의 로봇이 이동하여 N번칸에 도착하였을 때 총 두 가지뿐입니다. 2. 조금만 생각해보면 항상 로봇이 타는 번호가 1번이며 먼저 탄 로봇이 먼저 내리고 내리는 칸이 N번 칸이므로 로봇이 (N+1) ~ 2*N번 칸인 컨베이너 벨트 ..

문제 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이�� www.acmicpc.net 문제 풀이 1. 두 점을 연결하는 비용은 각 x, y, z좌표끼리 차의 최소 값이므로 N개의 행성을 연결하려면 좌표끼리의 차를 값으로 가지는 N - 1개의 간선을 찾아야 합니다. 2. 이는 아래의 관찰을 통해 각 축에 대해서 좌표를 정렬했을 때 인접한 점들의 차만 간선에 추가하는 방법을 통해 해결했습니다. 서로 인접한 세 점 A, B, C에 대해 모든 점을 연결할 때, ..

문제 www.acmicpc.net/problem/12107 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net 문제 풀이 모든 수의 약수인 1을 제외한 N-1개의 수로 게임을 진행했을 때의 결과로 N개의 수를 뽑는 상황을 생각해보면 아래와 같습니다. 1. N - 1개의 수로 게임했고, 마지막 순서가 상대(B)에게 갈 때 A가 처음 뽑은 수의 약수에 1을 포함한다면 똑같이 마지막 순서가 상대에게 가므로 (A)승리 2. N - 1개의 수로 게임했고, 마지막 순서가 나(A)에게 올 때 A가 처음 순서에 1만 집고 시작하면 마지막 순서가 상대에게 가므로 (A)승리 3. 따라서 N이 1..

문제 www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 문제 풀이 1. 문자열이 팰린드롬이 아닌 경우) 문자열 그 자체가 팰린드롬이 아닌 가장 긴 부분 문자열의 길이이므로 그 길이를 출력하면 됩니다. 2. 문자열이 팰린드롬인 경우) 일반적인 팰린드롬의 성질에 대해서 생각해볼 때, 문자열의 시작과 끝 중에서 한 글자만 빠져도 팰린드롬이 깨진 다는 걸 알 수 있습니다. 모든 문자가 같은 문자열일 경우 모든 부분문자열에 대해 각 ..

문제 www.acmicpc.net/problem/2381 2381번: 최대 거리 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다. www.acmicpc.net 풀이 절댓값을 풀어서 나오는 네 가지 경우는 아래의 꼴입니다. 1. $±((a + b) - (c + d))$ 2. $±((a - b) - (c - d))$ 각 식을 살펴보면 결국 두 점간의 거리를 구하는 게 x, y좌표 대, 소관계와 관계없이 좌표 간의 합(차)의 차이를 구하는 것과 같고, 이에 최대 거리를 구하는 것은 각 좌표 간 합(차)의 최대 값에서 최소 값을 빼는 것과 같습니다. 코드 #include using namespace std; int..