alpyrithm_알파이리즘

DP 2193 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 n을 Scanner로 입력받는다. 1번 규칙에 의해 n = 1 일 때는 1만 가능하다. n = 2 일 때는 1 뒤에 0만 올 수 있다. 2번 규칙에 의해 N자리에 0이 올 수 있는 경우는 앞의 숫자가 0 또는 1일 때이고, 1이 올 수 있는 경우는 앞의 숫자가 0일 때만 가능하다. 위의 규칙을 이용해서 개수를 세..

DP 11057 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 1 n의 범위가 1에서 1000이므로 3중 for문을 돌아도 시간 초과가 발생하지 않을 거라 생각했다. n을 Scanner로 입력받는다. n = 1 일 때는 0 - 9까지 모두 가능하다. n = 2 일 때는 0 뒤에는 0 - 9가, 1 뒤에는 1 - 9가, ..., 8 뒤에는 8 또..

DP 10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 이번 문제에서 중요한 부분은 정답을 1,000,000,000으로 나눈 나머지를 출력하는 것으로 해당 값들이 1,000,000,000 보다 큰 수일 수 있다는 부분이다. → int가 아닌 long으로 타입 지정해야 한다. 타입 설정이 따로 필요없는 파이썬을 주로 사용했기 때문에 이 부분에서 실수가 있었다.(기초를 잡자.) 계단 수의 경우 n = 1 일 때는 1 - 9까지 모두 가능하다. n = 2 일 때는 1 뒤에는 0 또는 2가..

DP 9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 n은 양수이며 11보다 작은 수이다. 정수 n이 주어졌을 때 1, 2, 3의 합으로 나타내는 규칙을 찾아야 한다. 정수 n-1에서 1을 더하면 n이 되고 마찬가지로 (n-2) + 2, (n-3) + 3은 n이다. 따라서 정수 n을 1, 2, 3의 합으로 나타내는 방법은 정수 (n-1), (n-2), (n-3)을 1, 2, 3의 합으로 나타내는 방법의 수의 합이다. n이 1일 때 1, 2일 때 2, 3일 때 ..

DP 11727 2Xn 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 n을 Scanner를 이용하여 입력받는다. 배열의 크기가 n+1인(인덱스가 0 ~ n 까지) 배열을 선언한다. 그리고 2 x n번째 직사각형을 타일로 어떻게 채울 수 있는가를 고민해야 한다. 먼저 2 x 1의 경우 2 x 1의 경우 1가지이다. 2 x 2의 경우 2 x 1을 2개 붙이는 경우, 1 x 2를 2개 붙이는 경우, 2 x 2 1..

보호되어 있는 글입니다.