[파이썬] 백준 11727 : 2xn 타일링 2

[파이썬] 백준 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 실버 3 DP 도저히 규칙을 못 찾아서 노가다로 경우의 수를 구해봤다. 1 : 1 2 : 3 3 : 5 4 : 11 5 : 21 ... 3번째 의 5는 1번째의 1에 2를 곱한 값과 2번째의 3을 더한 값과 같다는 사실을 발견했다. 이를 점화식으로 나타내면 dp[i] = dp[i-2]*2 + dp[i-1]가 된다. 코드 import sys n = int(sys.stdin.read..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 26.
• textsms

[파이썬] 백준 9461 : 파도반 수열

[파이썬] 백준 9461 : 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 실버 3 수학, DP 숫자들을 쭉 깔아서 보면 바로 규칙이 보일 것이다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9... i번째의 값은 i-3과 i-2번째의 값의 합으로 이루어져있는 피보나치 수열과 비슷한 규칙을 가지고 있다. import sys; input = sys.stdin.readline T = int(input()) for _ in range(..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 24.
• textsms

[파이썬] 백준 17626 : Four Squares

[파이썬] 백준 17626 : Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 실버 4 DP, 브루트포스 접근 DP문제에 대한 자신감을 박살내버리는 문제였다. 다른 사람 풀이를 보고도 좀처럼 이해가 되지 않아 골머리를 앓았다. 문제에 따르면 어떤 수든 간에 최대 4개가지의 제곱수의 합으로 표현이 된다고 해서 1부터 쭉 공책에 써봤다. 1 = 1^2 = 1개 2 = 1^2 * 2 = 2개..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 18.
• textsms

[파이썬] 백준 2579 : 계단 오르기

[파이썬] 백준 2579 : 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 실버 3 DP 접근 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 계단을 한 계단 밟을지, 두 계단을 밟을지를 선택할 수 있다. dp문제를 풀 때..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 13.
• textsms

[파이썬] 백준 8394 : 악수

[파이썬] 백준 8394 : 악수 https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 실버 4 수학, DP 접근 하나하나 경우의 수를 직접 계산해보면 피보나치 수열로 규칙이 나타난다는 것을 알 수 있다. 문제는 n의 범위가 어마어마하기 때문에 수가 커지면 커질수록 다루는 수가 기하급수적으로 증가한다는 점이다. 시간 초과하지 않으려면 구한 값의 마지막 자리를 미리 넣어주는 방법을 이용해야 했다. 코드 import sys n = int(sys.stdin.readline()) dp = [1] * (n+1) for i in range(2, n+1): dp[i] =..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms

[파이썬] 백준 1463 : 1로 만들기

[파이썬] 백준 1463 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 실버 3 DP 접근 1로 빼거나 2로 나누어지면 2로 나누거나 3으로 나누어지면 3으로 나눈다. 이걸 그대로 구현하면 10을 입력값으로 주었을 때 예외가 생긴다. 위의 방법을 그냥 분기로 구현하면 10 > 5 > 4 > 2 > 1 이렇게 총 4번이 되지만, 10 > 9 > 3 > 1로 총 3번이면 1로 만들 수 있는 방법이 있기 때문이다. 만약 입력 값에서 처음의 3가지 경우를 각각 사용했을 때 구해진 연산 횟수중에 가장 작은 값을 선택할 수 있다면 좋을 것이다. 문제를..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms