백준 알고리즘 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.
백준 알고리즘 2748 (피보나치 수 2) - C++, Python
[문제] 백준 알고리즘 2748 (피보나치 수 2) > https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 www.acmicpc.net 피보나치 문제, DP문제이다. N이 주어지고, N번째 피보나치 수를 출력하는..
2019. 10. 29.