-
2312. [Python]수 복원하기Python_알고리즘/Silver III 2023. 6. 4. 22:22
1. 문제
https://www.acmicpc.net/problem/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. 문제를 푸는데 도움이 되는 지식
- 정수론
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1448. [Python]삼각형 만들기 (1) 2023.06.06 1904. [Python]01타일 (0) 2023.06.05 1270. [Python]전쟁 - 땅따먹기 (0) 2023.05.30 2149. [Python]암호 해독 (0) 2023.05.30 2407. [Python]조합 (0) 2023.05.26