백준 알고리즘 2630 (색종이 만들기) - C++, Python
[문제] 백준 알고리즘 2630 (색종이 만들기) > https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net '분할 정복(Divide and Conquer)' 문제이다. 분할 정복은 보통 재귀함수의 응용인데, 원하는 조건을 만족하지 않으면 문제를 분할(=작은 부문제)해서 해결하는 방식으로 다시 재귀시킨다. 4등분을 하면..
2019. 11. 8.
백준 알고리즘 1149 (RGB거리) - C++, Python
[문제] 백준 알고리즘 1149 (RGB거리) > https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 집에 빨강, 초록, 파랑 중에 하나의 색을 칠하려는데, 이웃은 같은 색을 칠할 수 없다. 각 색깔에 대한 비용이 주어질 때, 모든 집을 칠하는 ..
2019. 11. 7.
백준 알고리즘 9461 (파도반 수열) - C++, Python
[문제] 백준 알고리즘 9461 (파도반 수열) > https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 나선에서 가장 긴 변의 길이를 갖는 정삼각형을 계속 추가하는 수열 문제이다. DP..
2019. 11. 4.