Coder's Cattitude

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 딱 보면 끝이 0인 애들은 뒤에 0이나 1이 올 수 있고, 끝이 1인 애들은 0밖에 못오는 것을 알 수 있다. 그래서 생각한게 0으로 끝나는 수와 1로 끝나는 수들의 개수를 따로 저장하는 것이었다. 그래서 1차원 배열이 아닌 2차원 배열로 dp를 만들어서 끝이 0인 수의 개수는 0열에, 끝이 1인 수의 개수는 1열에 저장하기로 한다. n 0으로 끝나는 수 1로 끝나는 수 1 - 1 2 10 - 3 100 101 4 1010, 1000 1001 5 10100, 100000, 10010 10101, 100001 위의 표를 개수로 나타내 보겠다 n 0으로 끝나는 수들의 개수 1로 끝나는 수들의 개수 1 0 1 2 1 0 3 1 1 4 2 1 5 3 2 .....

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 위의 그림을 보면 n이 1이고, 2인 경우를 제외하면 n이 3부터는 규칙이 생기는 것을 알 수 있다. 2 x n을 만들기 위해서는 2가지 방법이 있다. 2 x (n - 1) 인 경우에 1 x 2 타일 1개 붙이기 2 x (n - 2) 인 경우에 2 x 2 타일이나 2 x 1 타일 2개 붙이기 그래서 식으로 적으면 dp[n] = dp[n - 1] + dp[n - 2] * 2가 된다. 위의 그림을 보면 이해가 더 쉬울 것이다. 분홍색 형광펜으로 네모 표시를 한 부분들이 바로 이전 타일들에 추가된 부분들이다. 아래는 dp 식을 정리한 것이다. dp를 위한 배열을 만들 때, n이 아닌, n + 1 배열로 만드는 것이 편하다. 🔑 python 코드 # 2xN 타일링 2..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 이 문제는 조합을 사용해서 풀었다. 고등학교 확률과 통계 조합 단원에서, 집합 X에서 집합 Y로의 함수를 정의 할 때 조건 x1 < x2 이면, f(x1) < f(x2)를 만족하는 함수의 개수를 구하는 문제가 있다. 이 다리 놓기 문제는 다리 끼리 겹쳐지는 상황이 생기면 안되기 때문에 위의 그림에 적어놓은 것 처럼 저 조건을 사용해서 조합으로 풀 수 있다. 🔑 python 코드 #다리 놓기 import sys input = sys.stdin.readline T = int(input()) arr = [[int(i) for i in input().split()]for _ in range(T)] #조합 def nCr(n, m): ans = 1 d = 1 for i ..

문제 바로가기 => 줄세우기 🔒 문제 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다. 예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자. 3 7 5 2 6 1 4 아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 ..

문제 바로가기 => LCS 🔒 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. ⌨ 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 🖨 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 📚 예제 Ex) ACAYKP CAPCAK 4 📌 풀이 arr1과 arr2에 각각 문자열을 저장해준다. arr1의 문자열 길이를 n, arr2의 문자열 길이를 m으로 둔다. 조심해야할 점은 &#39;\n&#39;까지 문자열로 ..

문제 바로가기 => 가장 긴 증가하는 부분 수열 🔒 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ⌨ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 🖨 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 📚 예제 6 10 20 10 30 20 50 Ex) 4 📌 풀이 1번 풀이 (O(n^2)) *dp[ N ] = 0 ~ N - 1 인덱스에 저..

🔒 문제 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 ..