문제 링크https://www.acmicpc.net/problem/2417 문제 요약문제에서 주어진 N의 제곱근을 소수점에서 올림 한 값을 구하는 문제이다. 함정이 가득한 문제문제 자체는 상당히 간단해 이제 막 PS에 입문한 사람들이 연습용으로 풀기 좋은 문제로 보인다. 그리고 문제 번호도 2000번 대여서 뭔가 연습문제 같은 느낌도 상당히 든다.???: 제곱근을 수하고 소수점에서 올림을 하라니?! sqrt 함수를 이용하면 그냥 풀 수 있는 문제잖아! 이런 생각의 흐름을 거치고 나면 아래와 같은 코드를 작성하고 제출을 누르게 된다.#include #include using namespace std;int main() { unsigned long long n; cin >> n; ..
문제 링크https://www.acmicpc.net/problem/15989 문제 요약정수 N이 주어졌을 때, 1, 2, 3의 합으로 N을 나타내는 경우의 수를 찾는 문제이다. 순서만 다른 것은 같은 경우라는 것을 주의해야 한다. 문제 풀이이 문제는 전형적인 동적 계획법(dynamic programming, 이하 DP)로 해결할 수 있다. DP는 상향식과 하향식 두 가지 방법으로 구현할 수 있는데 보통은 하향식 방법이 구현이 쉽고 직관적이다. 하지만 슬라이딩 윈도우, 컨벡스 헐 트릭등 다양한 DP 최적화 전략을 이용하기 위해서라면 상향식 방법도 이용할 줄 알아야 하기 때문에 두 가지 방법으로 모두 구현을 해본다. 하향식으로 문제 풀기상향식으로 문제를 풀 때 가장 먼저 해야 할 일은 재귀적으로 문제를 해결..
문제 링크https://www.acmicpc.net/problem/17086 문제 요약임의의 점 \((i, j)\)의 안전거리는 \((i, j)\)에서 시작해서 아기 상어가 있는 곳까지의 최소 거리를 의미한다. 여기서 거리는 인접한 8방향(상하좌우 및 대각선)으로 이동한 칸 수로 계산한다. 격자판 위의 모든 점들 중에서 안전거리가 최대인 값을 찾아 출력하는 것이 이 문제의 목표이다. 문제 풀이기본적인 풀이너비 우선 탐색(이하 BFS)을 이용하면 임의의 점 \((i, j)\)에서 가장 가까운 아기 상어까지의 거리를 계산할 수 있다. 그리고 N과 M의 크기가 작으므로 모든 점들에 대해서 BFS를 한 번씩 돌려도 제한시간 내에 충분히 답을 구할 수 있다. 아래 더보기 버튼을 누르면 이 방법으로 푼 코드를 볼..
문제 링크https://www.acmicpc.net/problem/9376 문제 요약두 죄수 A, B가 최소한의 문을 열어 감옥에서 탈출하려고 한다. 한 죄수가 문을 열면, 그 문은 계속 열려 있어서 다른 죄수도 그 문을 이용할 수 있다.(원래 문제에서는 감옥 밖에 있는 상근이가 특별한 기술을 이용해 문을 열어준다고 되어 있지만, 문제를 더 쉽게 이해할 수 있게 내용을 살짝 바꿨다.) 문제 풀이가장 먼저 떠오르는 생각은 두 죄수의 상태를 동시에 관리하는 것이다. 하지만 죄수가 있을 수 있는 장소는 1만 곳이고, 이를 두 죄수의 상태로 표현하면 1억 가지의 경우의 수가 생긴다. 여기에 탈출을 위해 이용한 문의 개수까지 고려한다면 이 방법은 문제를 제한 시간 내에 풀 수 있는 방법이 아니다. 경우의 수 나누..
문제 링크https://www.acmicpc.net/problem/10021 문제 요약농부 John은 가뭄 때문에 N개의 농지에 물을 공급하기 위한 수로를 설치하려고 한다. 각 농지는 2차원 평면 위의 점 \((x_i, y_i)\)로 나타내며, 서로 다른 두 농지 \(i\)와 \(j\)를 연결하는 수로를 건설하는 비용은 \((x_i - x_j)^2 + (y_i - y_j)^2\)으로 계산한다. 이 문제는 모든 농지가 서로 물을 공급받을 수 있도록 수로를 설치하는 최소 비용을 계산하는것이 목표다. 제약 사항이 하나 있다면 수로를 건설하는 업자가 수로 건설 비용이 C 이상이 되는 것만 설치한다는 것이다. 문제 풀이이 문제에서 농지는 그래프의 노드로, 수로는 간선으로 모델링 할 수 있다. 이렇게 그래프로 모델..
문제 링크https://www.acmicpc.net/problem/17404 문제 요약N개의 집을 다음 두 개의 규칙에 맞게 빨강, 초록, 파랑 중 하나로 칠해야 한다.인접한 두 집의 색이 달라야 한다.1번 집과 N번 집의 색이 달라야 한다.각 집을 특정 색으로 칠하는 비용이 주어졌을 때, 모든 집을 규칙에 맞게 칠할 때 드는 최소 비용을 구하는 문제이다.원래 문제에는 규칙이 세 개 있지만, 이해를 돕기 위해 두 개로 정리했다. 문제 풀이이 문제는 동적 계획법(dynamic programming)을 이용해 해결할 수 있다. 먼저, 부분 문제를 해결할 수 있는 함수를 정의한다. \(findMinCost(idx, prevColor) =\) idx - 1번째 집을 prevColor로 칠했을 때, idx번째 ..
문제 링크https://www.acmicpc.net/problem/1022 문제 요약반시계 방향을 따라 소용돌이 모양으로 숫자를 채운 뒤, 주어진 범위의 숫자를 포맷에 맞게 출력하는 문제 문제 풀이이 문제를 푸는 방법에는 실제로 소용돌이를 만들어보는 시뮬레이션 방법과 특정 좌표의 숫자를 구할 수 있는 규칙을 찾는 방법 두 가지가 있다. 이 문제를 풀기 위해 접근할 때 보통 두 번째 방법을 많이 생각하는 것 같다. 하지만 입력으로 주어지는 수의 제한 범위와 현대 컴퓨터의 연산속도를 이용하면 직접 시뮬레이션을 돌려 푸는 방법도 있다는 것을 소개하고 싶다.풀이 1. 시뮬레이션모눈종이에 소용돌이 모양으로 숫자를 채우는 시물레이션을 돌려보는 상상을 해보자. 입력으로 주어지는 좌표의 최솟값은 -5,000이고 최댓값..
