[이코테] 15강 문제 '시각'

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다.

00시 00분 03초

00시 13분 30초

 

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다.

00시 02분 55초

01시 27분 45초

 

문제 조건

풀이 시간 15분, 시간 제한 2초, 메모리 제한 128MB

 

입력

첫째 줄에 정수 N이 입력됩니다.

 

출력

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력합니다.

---

'문제 접근'

삼중 반복문으로 3을 만날 때마다 count의 개수를 늘려가야 한다고 생각했는데 구현으로 옮기기 쉽지 않았다.

 

0부터 59까지의 3이 포함된 숫자는 개수가 총 16개로 정해져있는데, 그렇다고 초와 분 변수값이 3일 때, 13일 때 등등 노가다로 구하는 것은 아닌 것 같아 고민에 빠졌다.

 

한참을 고민해서야 번뜩 떠오른 아이디어..

시, 분, 초 모두 10으로 나눠 나머지가 3이면 카운트 해주되 몫 또한 3이면 또 카운트 해주면 되겠다고 생각했다.

 

but.. 대차게 실패 (아랜 오답 코드)

n = int(input())

cnt = 0

for h in range(n+1):
  for m in range(60):
    for s in range(60):
      if h % 10 == 3:
        cnt += 1
        
      # 30번대 수일 때와 아닐 때의 케이스를 나눠야 함
      if m // 10 == 3:
        cnt += 1
        if m % 10 == 3:
          cnt += 1
      else :
        if m % 10 == 3:
          cnt += 1

      if s // 10 == 3:
        cnt += 1
        if s % 10 == 3:
          cnt += 1
      else :
        if s % 10 == 3:
          cnt += 1

print(cnt)

조건을 잘못 설정했는지 n이 5일 때 output은 11475가 됐어야 했는데 15120이 나왔다.

아직 어느 부분에서 cnt 값을 중복해서 늘렸는지 모르겠어서 남겨뒀는데 코드 분석을 제대로 다시 해봐야겠다.

만약 어디가 잘못됐는지 아시는 분 있으면 댓글 남겨주세요.. :)

 

해결 완료

n = int(input())

cnt = 0

for h in range(n+1):
  for m in range(60):
    for s in range(60):
      if h % 10 == 3 or m // 10 == 3 or m % 10 == 3 or s // 10 == 3 or s % 10 == 3:
        cnt += 1
        
print(cnt)

시, 분, 초를 따로 분리하여 카운트를 하는 게 아니라, 내가 구하고자 하는 값은 전체 시간에서의 3의 개수이기 때문에 if문 하나에 'or'로 연결해 전체 조건 중 하나씩 들어맞을 때마다 카운트를 하니 해결할 수 있었다.

 

'문제 해결 아이디어'

가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제로, 전형적인 완전 탐색 문제

 

'정답 코드'

n = int(input())

cnt = 0

for h in range(n+1):
  for m in range(60):
    for s in range(60):
      if '3' in str(h) + str(m) + str(s) :
        cnt += 1

print(cnt)

중첩 반복문을 잘 알고있는지, 문자열을 잘 이해하고 있는지를 묻고 있는 문제다.

 

'돌아보며'

머리에 번뜩 떠오른 아이디어를 소스코드로 만들어 구현해내는 과정이 생각보다 어렵다..

그리고 이상한 고집이 있어 처음 떠올린 아이디어로만 문제를 해결해나가려 하는데 다음부터는 여러 가지의 아이디어는 아니더라도 다른 방법 또한 떠올릴 수 있도록 노력해야겠다. 화이팅!