BOJ 2331 반복 수열

LONGNEW·2021년 1월 16일
0

BOJ

목록 보기
56/333

https://www.acmicpc.net/problem/2331
시간 2초, 메모리 256MB
input :

  • A P(1 ≤ A ≤ 9999)(1 ≤ P ≤ 5)

output :

  • 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수

조건 :

  • A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복

...미친놈인가

계산을 틀리네;;;

일단 첫째 자리의 숫자 p제곱.
둘째 자리의 숫자 p제곱.,.... 순서로 가기 때문에
10으로 나머지를 구해서 제곱을 하자.

for i in range(10000):
    num = data[i]
    next_num = 0
    while num > 0:
        next_num += (num % 10) ** p
        num = num // 10
    data.append(next_num)

제곱 계산후에 다른 나머지들도 동일한 계산을 거친 후 data리스트에 넣어 수열을 만든다.
10000의 경우 임의로 그냥 지정했다 ;;

맨 처음엔 괜히 나머지를 저장하는 변수 만들고.
반복문 써가지고 곱하려다가 중간에 꼬여서 틀림 ;;

그리고 반복되는 수열을 구분해야 하는데 어떻게 하는가?
일단 위의 수를 만들어서 한 100개 정도 출력 해보자.

57 3
[57, 468, 792, 1080, 513,
153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153, 153]

57 4
[57, 3026, 1393, 6724, 3969, 14499, 13635, 2084, 4368, 5729, 9603, 7938,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138, 4179, 9219,
13139, 6725, 4338, 4514, 1138]

반복이 일어나는 숫자의 경우 그냥 data 리스트에 그 숫자가 더 포함되어 있다. 그러면 이를 어떻게 찾아내느냐?
리스트 슬라이싱을 사용해서 in을 쓰자. in 때문에 몇 번 데이긴 했는데 그냥 편하니까 쓰도록.

while True:
    if data[idx] in data[idx + 1:]:
        break
    cycle.append(data[idx])
    idx += 1

정답 코드 :

import sys

a, p = map(int, sys.stdin.readline().split())
data = [a]
cycle = []

for i in range(100):
    num = data[i]
    next_num = 0
    while num > 0:
        next_num += (num % 10) ** p
        num = num // 10
    data.append(next_num)
print(data)
idx = 0
while True:
    if data[idx] in data[idx + 1:]:
        break
    cycle.append(data[idx])
    idx += 1
print(len(cycle))

0개의 댓글