2312. [Python]수 복원하기

1. 문제

 

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

2312번: 수 복원하기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 정수론

 

3. 파이썬 코드

 

# 테스트 케이스 갯수
N = int(input())
# 갯수만큼 반복문 시행
for _ in range(N):
    # 소인수 분해할 수
    number = int(input())
    # 각각 몇개가 들어있는지 체크할 딕셔너리
    num_dict = {}
    # 시작값 2부터
    check = 2
    # input으로 들어온 값이 1보다 큰경우 계속 반복문
    while number>1:
        # 만약 check로 나누어 떨어질 경우
        if number%check == 0:
            # 딕셔너리에 값이 있는지 확인하고 없으면 추가 있으면 1 증가
            if check in num_dict:
                num_dict[check] += 1
            else:
                num_dict[check] = 1
            # number 값을 check로 나눈 몫을 다시 넣어줌
            number //= check
        # 나누어 떨어지지 않을 경우 check 값을 1증가
        else:
            check += 1
    for k,v in num_dict.items():
        print(k,v)

 

4. 문제를 풀고난 후 생각

 

• 그냥 들어온 숫자를 가지고 계속해서 나눠가며 딕셔너리를 통해서 문제를 해결하는 방식을 채용했다.
• N값으로 들어오는 수의 범위가 크지않고 적당한 수의 범위였기 때문에 딕셔너리와 반복문을 통해서 값을 눠가며 나누어 떨어지지 않는 경우 값을 +1 해주는 방식으로 input 값을 계속해서 나눠가며 갯수를 체크해줬다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 정수론