⌚ 시각

문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하라.

입력 조건

첫째 줄에 정수 N(0<=N<=23)이 입력된다.

출력 조건

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

입력 예시

5

출력 예시

11475

---

🐹 완전 탐색(Brute-Forcing)

완전 탐색 알고리즘은 가능한 경우의 모든 수를 하나 하나 검사해보는 방법이다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있기 때문에, 데이터의 개수가 큰 경우에는 실행 시간이 무지막지하게 커질 수 있다. 대략적으로 전체 데이터 수가 100만 개 이하인 경우 완전 탐색 적용을 고려해볼만 하다고 한다. 해당 문제의 경우 00시 00분 00초 부터 조건에 맞는 경우를 찾으면 되는데, 탐색해야 할 경우의 수를 먼저 따져보면 하루는 24시간이고 60분이고 60초이므로 모든 경우의 수는 86400 개이다. 이러한 경우에는 확인 해야 할 데이터 수가 매우 작은 편이기 때문에 그냥 하나하나 다 따져보는 것이 가장 명확한 방법이 될 수 있겠다.

해당 문제의 경우 3중 for 문을 이용하여,
00 시 00분 00초 ~(INPUT)시 59분 59초
모든 경우의 수에 대해 조건을 만족하면 count를 하나씩 늘려가는 방안을 택하였다.

if("3이 하나라도 포함되는가?") count ++;
에서 if 문 내의 조건이 조금 길어지는 감이 있어, 따로 bool 형을 반환하는 check(int hour, int minute, int second) 함수를 만들어 이용했다.

#include <iostream>

/*

하루 : 24시간 * 60분 * 60초 = 86400
중에 3이 하나라도 있으면 count!

*/

using namespace std;

bool check(int hour, int minute, int second)
{
  if(hour%10 == 3 || minute%10 == 3 || minute/10 == 3 || second%10 == 3 || second/10 ==3)
    return true;
  else
    return false;
}

int main()
{
  int hour;
  cin >> hour;
  int count = 0;

  for(int i = 0 ; i <= hour; i++)
    for(int j = 0; j< 60; j ++)
      for(int k = 0 ; k < 60; k ++)
        if(check(i,j,k)) count++;

  
  cout << count;

  return 0;
}