HS_development_log

문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 기존 RGB거리 문제에서 첫집과 마지막집도 이웃이라는 조건이 추가된문제 따라서 원형구조를 이룬다. 첫집과 마지막집의 색깔이 달라야하므로 첫번째집의 색을 고정하고 답을구한뒤 3가지의 색깔중..

문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 기존 타일 채우기 문제는 2*n 이었지만 3*n으로 늘었다. 세로에 3만큼의 크기를 채워야하므로 n이 홀수 일때는 타일을 채울 수 있는 경우의수가 없다. 또한 n이 2씩 늘어날때마다 만들수 있는 방법이 2가지씩 늘어나는 것에 유의해서 점화식을 세우면 된다. 알고리즘 기본적으로 dp[i] = dp[i-..

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합에서 하나를 제거할 수 있다는 조건이 붙은 문제. 처음에는 하나를 제거할때 마다 모든 경우의 수를 계산해보려고 했다. 그러나 아래의 문제점이 발견해서 다른 해결법으로 풀었다. 1. 시간 복잡도를 O(N)에 해결할경우 메모리를 많이써야해서 메모리 초과 2. 시간복잡도를 O(N^2)에 해결할 경우 시간 초과. 그래서 k번째 수를 제거하는 연속 합일 경우 k-1번째까지의 연속합과 k+1부터의 연속합을 ..

문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 알고리즘 자릿수가 n인 i로 끝나는 오르막수를 dp[n][i]로 정의한다 자릿수가 n인 오르막수의 개수는 자릿수가 n인 0부터~9까지로 끝나는 오르막수를 다 더하면 된다. 나머지 연산을 해서 출력한다. 소스코드 1 2 3 4 5 6 7 8 9 10 1..