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))
