UP

문제 풀기 : 1463번 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라. 문제풀이 1로 만들기 위한 연산의 최소 사용 횟수를 구하는 문제이다. 하나의 숫자에 3가지 연산을 계속해서 수행해야 하기 때문에 중복연산이 동반되어 DP로 푸는 것이 좋다. 최적의 연산 횟수를 저장하는 DP 테이블을 생성한다. 현재의 정수X에 연산이 수행될 때..

문제 풀기 : 11727번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 문제풀이 다음은 n = 4 까지의 경우의 수를 따져본 것이다. +추가) n = 2일때 2x1을 2개 이어붙인 부분과 1x2를 2개 이어붙인 부분은 같은 모양으로 n=2의 경우의 수는 3가지가 아니라 2가지가 맞습니다! 그림을 잘못 그렸습니다. 참고해주세요!! n = 3 부터 보면 n = 2과 n = 1..

문제 풀기 : 11726번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하라. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 문제풀이 다음은 n = 4 까지의 경우의 수를 따져본 것이다. n = 3 부터 보면 n = 1과 n = 2의 타일 모양이 그대로 들어있고 n = 4 를 보면 n = 2와 n = 3의 타일 모양을 그대로 가지고 있다는 것을 알 수 있다. 해당 규칙을 파악한대로 점화식을 작성해보면 dp[i] = dp[i-2] + ..

문제 풀기 : 10844번 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라. 0으로 시작하는 수는 없다. 문제풀이 길이가 N일 때 앞뒤로 차이가 1이 나는 숫자가 몇 개인지를 구하는 문제이다. 뒤에 있는 숫자를 기준으로 앞에 올 수 있는 숫자의 경우의 수를 구할 것이다. 자리수마다 각각의 숫자 앞에 올 수 있는 경우의 수가 다르므로 2차원 DP 테이블을 만든다. dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에 올 수 있는 일의 자리 수 ] ..

문제 풀기 : 11057번 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 오르막 수는 수의 자리가 오름차순을 이루는 수. 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하라. 수는 0으로 시작할 수 있다. 문제풀이 DP 테이블을 2차원 배열로 만든다. dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에..

문제 풀기 : 2193번 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 이친수는 1. 0과 1로만 이루어진 수 2. 0으로 시작하지 않는다. 3. 1이 두 번 연속으로 나타나지 않는다. N(1 ≤ N ≤ 90) N자리 이친수의 개수를 구하라. 문제풀이 n = 5 까지의 케이스를 찾아본다. n = 4(하늘색 표시) 부터 살펴보면 n = 2와 n =3의 경우의 수가 다 들어가 있는 것을 볼 수 있다. → 10, 00, 01 n = 5(빨간색 표시) 부터 살펴보면 n = 3와 n =4의 경우의 수..