매일 조금씩

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 DP를 이용하여 풀었다. 작은 문제들의 답을 구한다. dp[2] = 1, N이 2일 때는 최소 횟수가 1이다. (2으로 나눔) dp[3] = 1, N이 3일 때는 최소 횟수가 1이다 (3으로 나눔) ..

문제 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 풀이 완전 탐색으로 풀면 시간 초과가 발생한다. 가만 보니 2 x n 타일링 문제와 동일하다. 아래 문제에서 세로 타일 한개를 1칸, 가로타일 두 개를 2칸으로 해당 문제에 대입할 수 있다. DP문제로 점화식을 이용해서 풀 수 있다. 2021.10.29 - [Alogirthm/Programmers]..

문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 풀이 DP 방식으로 풀 수 있다. 코드는 정말 간단한데 점화식을 세우는 게 쉽지 않다. 타일이 가로로 끝나는 것과 세로로 끝나는 것을 분류해보면 아래와 같다. 가로길이가 i일 때, 타일링의 경우의 수는 = i-1의 경우의 수와 i-2의 경우의 수를 합한 것이다. i-1의 경우의 수에서 세로 타일을 붙임 i-2의 경우의 수에서 가로 타일을 붙임 ..