문제 링크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이고 최댓값..
