[BOJ] 1065번 한수

BOJ 1065번 한수

한 자리수와 두 자리수일 때는 무조건 한수의 조건이 만족된다.
그래서 N이 100 미만일 땐 N을 그대로 출력하면 되고, 그 이상이면 세 자리수부터 답을 구한 뒤 99를 더해주면 된다.

풀이

#include <iostream>
using namespace std;

int main() {
  int N;
  cin>>N;

  if(N<100) {
    cout<< N;
    return 0;
  }
  
  if(N==1000) N--;

  int answer = 99;
  int digit[3];
  int tmpDigit[2];
  digit[0] = N%10;
  digit[1] = (N%100)/10;
  digit[2] = (N%1000)/100;

  for(int i=1;i<=digit[2];i++){
    if(i*100+(i)*10+(i)<=N) answer++;
    for(int j=1;j<=9;j++){
      if(i+j <= 9 && i+j*2 <= 9 && i*100+(i+j)*10+(i+j*2)<=N) answer++;
      if(i-j >=0 && i-j*2 >= 0 && i*100+(i-j)*10+(i-j*2)<=N) answer++;
    }
  }

  cout<<answer;
  return 0;
}

i : 1부터 N의 100의 자리수만큼 반복 j : 1부터 9까지 반복한다. i+j는 십의 자리수, i+j2는 일의 자리수가 되며 각 자리수가 [i][i+j][i+j\2]가 되는 수가 N보다 크지 않으면 answer를 증가시킨다.

시간복잡도

2중 for문이지만 N의 백의 자리수만큼 10번 반복하므로 O(N)보다는 작을 것 같은데, 계산을 잘 못하겠다...

다른 풀이

다른 사람의 풀이를 보니 100부터 N까지 하나씩 다 체크했다. O(N)이지만 코드도 간결하고 알아보기 쉽다.

#include <stdio.h>
int main(){
    int n, count = 99;
    scanf("%d", &n);
    if(n < 100) printf("%d", n);
    else{
        for(int i = 100; i<=n; i++) if(i%10 + i/100 == i/10%10*2) count++;
        printf("%d", count);
    }
}