[알고리즘][완전탐색] 완전탐색

완전탐색

완전탐색 알고리즘은 말그대로 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 말한다.

예를 들어 숫자 N이 주어지고 00시 00분 00초에서 N시 59분 59초까지 숫자 3이 들어가는 시간의 개수를 출력하는 문제가 있다고 해보자.

이 문제는 가능한 모든 경우의 수를 탐색해서 조건에 해당하는 경우를 카운트함으로써 해결할 수 있다.

---

코드

N = int(input())
count = 0

for i in range(N+1):
	for j in range(60):
    	for k in range(60):
        	if '3' in str(i) + str(j) + str(k):
            	count += 1

print(count)

# 출력 결과
# 11475

이 문제의 경우 분, 초는 고정되어 있으므로, 시간에 3이 들어가는 경우 3600, 그렇지 않은 경우 1575로 계산해서 더하는 방식도 가능하다.

N = int(input())
count = 0

for i in range(N+1):
    count += 3600 if '3' in str(i) else 1575

print(count)

# 출력결과
# 11475