-
1527. [Python] 금민수의 개수Python_알고리즘/Silver I 2023. 8. 30. 19:24
1. 문제
https://www.acmicpc.net/problem/1527
1527번: 금민수의 개수
첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 재귀
3. 파이썬 코드
def DFS(num): # cnt 변수 글로벌 선언 global cnt # num 값에 "4" or "7" 추가 num = str(num) # 범위 내에 있으면 cnt 증가 if A <= int(num) <= B: cnt += 1 # B보다 크면 재귀 종료 if int(num) > B: return # 그 외의 경우 문자열로 4, 7 붙여가며 재귀 시행 else: for i in ["4", "7"]: DFS(num+i) A, B = map(int,input().split()) cnt = 0 # 초기갑 4로 시작, 7로 시작한 값들 계산 DFS(4) DFS(7) print(cnt)
4. 문제를 풀고난 후 생각
- A, B 범위 값을 설정해둔 후 초기값 4, 7로 둔 후 문자열 + 로 4, 7 을 붙여서 재귀 함수를 사용해서 조건에 부합할 경우 cnt 값을 +1 해주는 방식으로 접근했다.
- 초기값으로 각각 4, 7 들어왔을 경우
초기값 : 4 => 44 => 444 (값이 넘으면) 447(넘으면) 47 => 474(넘으면) 477(넘으면) 4로 돌아옴
초기값 : 7 => 74 =>744 (값이 넘으면) 747(넘으면) 77 => 774(넘으면) 777(넘으면) 7 로 돌아옴
- 이런 구조를 반복하며 A~B 사이에 값이 있는 경우 cnt 값 1증가
5. 문제를 푸는데 도움이 되는 지식
- 재귀
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1926. [Python]그림 (0) 2023.12.09 1342. [Python]행운의 문자열 (1) 2023.12.08 1421. [Python]나무꾼 이다솜 (2) 2023.12.07 2667. [Python]단지번호붙이기 (0) 2023.06.04 1697. [Python]숨바꼭질 (0) 2023.03.09