SilentWalk

문제: https://www.acmicpc.net/problem/11726(백준) 문제: https://programmers.co.kr/learn/courses/30/lessons/12900(프로그래머스) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 프로그래머스의 [멀리 뛰기] 문제와 사실상 같은 문제이다. 멀리 뛰기 게시글에 해당 내용을 정리 해 놓았다. 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..

문제: https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이과정 문제를 서술하는 방식만 바뀌었을 뿐, 2N 타일링 문제와 완전히 동일한 문제이다. 그래서 1칸 점프와 2칸 점프를 각각 다음과 같이 치환하여 생각할 수 있다. 이제, 높이가 2이고 가로길이가 N인 공간에 크기가 1 * 2인 타일을 놓는 방법의 수를 몇가지 더 찾아보면 다음과 같다. 이 그림..

등굣길 풀이과정 주어진 n과 m에 대하여 이동 가능한 길을 grid로 나타낼 수 있다. 예를 들어 n = 3, m = 4이면 아래 그림과 같다. 문제의 제한 조건으로 이동 방향은 우측 및 하단 뿐이므로, 출발지점에서 우측과 하단으로 이동 가능한 방법의 수는 아래의 그림과 같이 나타낼 수 있다. 각각 오른쪽으로만 계속 이동하거나, 하단으로만 계속 이동해야 도달할 수 있는 위치이므로 이동가능한 방법의 가짓수는 모두 1이다. 나머지 비어있는 cell 들로 이동할 수 있는 방법은, 바로 위 cell에서 아래로 이동하거나 바로 왼쪽 cell에서 우측으로 이동하는 것 뿐이므로 나머지 각각의 cell들에 대한 이동 가능한 방법의 수는 바로 위쪽 cell까지 이동 가능한 방법의 수 + 바로 왼쪽 cell까지 이동 가능..

N으로 표현 풀이과정 각 단계별로(숫자 N을 i번 사용) 표현할 수 있는 수는 크게 두 종류로 구분할 수 있다. N을 i번 이어 붙인 경우 이전 단계의 결과를 서로 사칙연산한 결과 예를 들어, 4번 째 단계라면 다음과 같은 경우의 수를 갖는다. N을 4번 이어붙인 경우 N을 3개 사용한 경우(바로 이전 단계)와 N을 1개(= 4 - 3)만 사용한 경우의 사칙연산 N을 2개 사용한 경우(전전 단계)와 N을 2개(= 4 - 2)만 사용한 경우의 사칙연산 N을 1개 사용한 경우(전전전 단계)와 N을 3개(= 4 - 1)만 사용한 경우의 사칙연산 이를 통해 특정 숫자 N만을 활용하여 어떤 임의의 정수 k를 만들 수 있는 방법은 다음과 같이 전개하여 찾을 수 있다. i개의 N을 사용하여 표헌할 수 있는 모든 수를..