[Baekjoon] 9461 파도반 수열, 10844 계단 수, 1924 2007년

백준 9461 파도반 수열

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

나선을 따라 가며 n번째의 삼각형의 변의 길이를 찾는 문제이다.

삼각형의 변의 길이는 이전 삼각형과 5번째 전 삼각형의 변의 길이를 더한 것과 같다는 점을 이용해 문제를 해결할 수 있다.

정삼각형의 한 각의 크기는 60도이므로, 이 점을 이용해 5번째 전의 삼각형을 추론할 수도 있을 것이다.

코드는 다음과 같다.

t = int(input())
for i in range(t):
    n = int(input())
    lst = [1, 1, 1, 2, 2]
    if n < 5:
        print(lst[n-1])
    else:
        for i in range(5, n):
            lst.append(lst[i-1] + lst[i-5])
        print(lst[n-1])

 

 

 

---

 

 

 

백준 10844 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

n을 입력받고, n자리의 계단 수가 몇 개 있는지 출력하는 프로그램이다.

처음에는 dfs로 풀려 했지만, 그러면 시간 복잡도가 O(2^n)에 가깝게 나와 다른 방법을 생각했다.

처음에는 3자리 이상부터는 각 자리에서 2개씩 갈라지고, 이전 경우중 0과 9만 하나이므로

이전 경우의 수 * 2 - 2

가 n자리까지의 경우의 수를 구하는 공식이라고 생각했다.

 

하지만, 처음부터 틀림이 나와 다른 방법을 생각해야 했다.

 

그래서 그림을 그려 보다 어쩌면 이 문제는 예전에 풀었던 백준 1932 최소 삼각형 문제와 그림이 비슷해 보여 해당 방법과 비슷한 방법으로 풀 수 있지 않을까 하는 생각이 들었다.

 

그래서 DP방식으로 생각해 보니, 해당 경우의 i번째 자리는 이전 자리의 i-1번째와 i+1번째 자리의 경우의 수를 합친 것과 같아지므로 공식은 결국 이렇게 된다.

이전 경우의 i-1 번째 자리의 경우의 수 + 이전 경우의 i+1번째 자리의 경우의 수

최종 코드는 다음과 같다.

import copy
n = int(input())
res = [0] + [1] * 9
p_res = []
for i in range(n-1):
    p_res = copy.copy(res)
    res = [0] * 10
    for j in range(10):
        if j > 0:
            res[j] += p_res[j-1]
        if j < 9:
            res[j] += p_res[j+1]
print(sum(res) % 1000000000)

 

 

---

 

 

백준 1924 2007년

https://www.acmicpc.net/problem/1924

1924번: 2007년

2007년 1월 1일이 월요일일 때, 2007년 x년 y일이 무슨 요일인지 출력하는 프로그램이다.

 

x를 입력받으면 이를 그때까지의 일수로 변환시키고, y를 더해 7로 나머지연산한 후, 이를 days리스트의 맞는 요일과 매칭시켰다.

 

코드는 다음과 같다.

x, y = map(int, input().split())
days = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
day_num = 0
for i in range(x-1):
    day_num += months[i]
day_num += y
day_num %= 7
print(days[day_num])