Coder's Cattitude

🔒 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. ⌨ 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 🖨 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 📚 예제 Ex) 10 1 📌 풀이 쉬운 계단 수의 심화 버전인것 같다. 어떻게 풀어야할 지 많은 고민을 했는데 비트마스킹을 사용하니까 쉽게 풀렸다. dp[계단 수][일의 자리 수][0~9 중 어떤 수들 사용했는 지] 로 행렬을 만든다. 2차원 배열을 사용..

🔒 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. ⌨ 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 🖨 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 📚 예제 Ex1) 1 9 Ex2) 2 17 📌 풀이 dp[계단 수][일의 자리 수] 로 행렬을 만든다. 행렬에는 각 인덱스 별 만들 수 있는 계단 수를 저장한다. dp[n][m]으로 가정하자. N == 1 일 때 n == 0 일 때, m이 0인 경우를 제외하고는 모두 1이다. m이 0인 경우는 0이다. (0으로 ..

🔒 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. ⌨ 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,00..

🔒 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. ⌨ 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 🖨 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 📚 예제 Ex) 5 7 3 8 8 1 0 2 7 4 ..

🔒 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. ⌨ 입력 첫째 줄에 1보다 크거나 같고, 10 ** 6보다 작거나 같은 정수 N이 주어진다. 🖨 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 📚 예제 Ex1) 2 '''python 1 ''' Ex2) 10 '''python 3 ''' 📌 풀이 dp[정수N+1] 행렬을 만든다. (N이 아니라 N+1개의 인덱스를..

🔒 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. ⌨ 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 🖨 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 📚 예제 Ex1) 2 2 Ex2) 9 55 📌 풀이 고등학교 때 풀던 확통 문제가 생각나는 문제이다. 수학 문제를 푸는 기분이었다. dp 행렬에 직사각형의 채우는 방법의 수를 저장 할 것이다. 따라서 dp[가로 길이]로 행렬을 만들어준다 가로 길이가 1이면 dp[0] = 1이다. 가로 길이가 2이면 dp[1] = 2이다. 가로 길이가 3이상이면 dp를 식으로 나타 낼..