UP

문제 풀기 : 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의 경우의 수..

문제 풀기 : 5014번 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 스타트링크는 총 F층으로 이루어진 고층 건물이다. 스타트링크가 있는 곳의 위치는 G층이고 지금 있는 곳은 S층이다. 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) 강호가 ..

문제 풀기 : 1525번 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 최소 이동 횟수 구한다. 문제풀이 모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다. 빈칸인 부분의 상, 하, 좌, 우와 빈칸을 바꿔가며 탐색한다. 이 때, 위의 표를 만..

문제 풀기 : 2251번 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 때, 한 물통이 비거나 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수..

문제 풀기 : 1963번 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 입력은 항상 네 자리 소수만(1000 이상) 주어지며 주어진 두 소수 A에서 B로 바꾸는데 필요한 최소 단계를 구한다. 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 한다. 문제풀이 모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다. 우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다. 그 다음은 각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바..