[백준(Baekjoon)] 2502 떡 먹는 호랑이

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에  준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.  

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째  날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

 

입력

첫째 줄에는 할머니가 넘어온 날 D (3 ≤ D ≤ 30)와 그 날 호랑이에게 준 떡의 개수 K (10 ≤ K ≤ 100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 

 

입력	출력
6 41	2 7
7 218	10 21

---

나의 풀이

[Python(파이썬)]

day, ricecakenum = map(int, input().split())
tree, i = [0, day], 1
while i != len(tree):
    now = tree[i]
    if now > 2:
        tree.append(now - 1)
        tree.append(now - 2)
    i += 1
onecnt, twocnt = tree.count(1), tree.count(2)

for j in range(ricecakenum//twocnt, 1, -1):
    minusb = ricecakenum - twocnt * j
    if minusb % onecnt == 0 and int(minusb // onecnt) != 0:
        print(int(minusb // onecnt))
        print(j)
        break

 

---

풀이 과정

1. onecnt, twocnt 구하기
2. a, b 구하기 

 

1.  onecnt,  twocnt 구하기

 

이 문제는 구현을 어떻게 해야 할지 알고리즘을 생각하는데 시간이 좀 걸렸다. 

그래서 계속 손으로 이것저것 적어보고 그려보면서 생각을 해나갔다. 

 

첫째 날에 떡을 2개 주었고, 둘째 날에는 떡을 3개 주었다면 셋째 날에는 2+3=5개, 넷째 날에는 3+5=8개, 다섯째 날에는 5+8=13개, 여섯째 날에는 8+13=21개를 주어야만 무사히 산을 넘어갈 수 있다.

 

그러다 뭔가 할머니가 넘어온 날의 떡의 개수를 첫째 날 둘째 날의 개수만으로 바꿀 수 있겠다는 생각을 했다. 

 

첫째 날에 떡을 a개 주었고 둘째 날에 b개 주었다고 생각하고 보면

3일째는 a + b

4일째는 a + 2b

5일째는 2a + 3b가 된다.

 

ex) a = 2(첫째 날 2개), b = 3(둘째 날 3개)를 줬다면 

5 = a + b = (2+3)

8 = a + 2b = (2 + 2*3)

13 = 2a + 3b = (2*2 + 3*3)

 

위처럼 생각했으면 이제 넘어온 날에 a와 b가 각 각 몇 개씩 들어가는지 계수를 찾아야 한다. 

아래 그림을 그려보며 뭔가 이진트리 같다는 생각을 했고 어떻게 구현을 할지 감이 잡히기 시작했다. 

 

 

 

 

 

 

 

 

할머니가 넘어온 4일째 떡의 개수 = 1a + 2b 

 

 

할머니가 넘어온 6일째 떡의 개수 = 3a + 5b

 

따라서 예제 입력인 6 41로 보면 41 = 3a + 5b

 

tree, i = [0, day], 1
while i != len(tree):
    now = tree[i]
    if now > 2:
        tree.append(now - 1)
        tree.append(now - 2)
    i += 1

트리를 만들어서 인덱스 0에는 0을 넣고 인덱스 1(루트)에는 할머니가 넘어온 날(day)을 넣는다. 

그리고 그 아래 자식들을 넣어준다. (1, 2는 자식 노드가 없기 때문에 2 초과할 때만 append) 

 

tree에서 1의 개수는 a의 계수(onecnt)가 되고 2의 개수는 b의 계수(twocnt)가 된다. 

onecnt, twocnt = tree.count(1), tree.count(2)

ricecakenum(마지막 날 떡의 개수) = onecnt * a(첫째 날 떡의 개수) + twocnt * b(둘째 날 떡의 개수) 

 

 

2. a, b 구하기

 

이제 onecnt(a의 계수)와 twocnt(b의 계수)를 구했으니 a와 b를 구해야 한다. 

 

a = 첫째 날 떡의 개수

b = 둘째 날 떡의 개수

 

for j in range(ricecakenum//twocnt, 1, -1):
    minusb = ricecakenum - twocnt * j
    if minusb % onecnt == 0 and int(minusb // onecnt) != 0:
        print(int(minusb // onecnt))
        print(j)
        break

 

문제에서 정수 A, B (1≤A≤B)라고 했으니 

ricecakenum//twocnt(b가 될 수 있는 최대 정수)부터 구하고

ricecakenum - twocnt * j(b가 될 수 있는 정수)가 onecnt로 나눠지는지 구해서 나눠 떨어진다면 출력하고 나눠 떨어지지 않는다면 for문을 계속한다. 

 

ex) 6 41

41 = 3a + 5b

 

1) ricecakenum // twocnt = 41 // 5 = 8(b가 될 수 있는 최대 정수) -> for문 range(8, 1, -1)

2) (ricecakenum - twocnt * j)  % onecnt = (41 - 5 * 8) % 3 = 1 % 3 = 1 -> 0이 아님 -> for문 넘어감

3) j = 7

4) (ricecakenum - twocnt * j)  % onecnt = (41 - 5 * 7) % 3 = 6 % 3 = 0 -> 0임

5) a = int(ricecakenum - twocnt * j // onecnt) = (41 - 5 * 7) // 3 = 2 출력

6) b = j = 7 출력

 

※ 첫째 날 주는 떡의 개수가 0이 될 수는 없으므로 주의해야 한다.  ->  int(minusb // onecnt) != 0

 

 

 

---

문제 출처

2502번: 떡 먹는 호랑이