증가와 감소(BOJ31801번)

문제

이미지 클릭

문제 설명

이 문제는 [a, b] 범위에 어떤 자연수 x가 있다고 한다면 x의 자릿수를 n자릿수라고 해봅시다. 첫 번째 자릿수에서 n번째 자릿수까지 x가 순서대로 증가하다가 감소만 하는 숫자를 카운팅 하는 문제입니다. 예를 들면 만약 x가 1234321이라면 x는 1~4까지 증가하다가 이후에는 오직 감소만 하기 때문에 x은 옳은 예제가 됩니다. 하지만 x가 1234322라면 1~4까지 증가하는 것은 맞지만 그 이후 부분에서 22는 감소하지 않기 때문에 틀린 예제가 됩니다.

문제 해설

기본적으로 120 미만의 숫자는 증가하다가 감소하는 숫자가 없기 때문에 120보다 작은 수는 0을 출력해 주었습니다.

if(m<120) {
   cout<<0<<"\n";
}

만약 120보다 작지 않다면 탐색을 해주어야 하는데 저는 문자열을 이용하여서 증가하고 감소하는 문제를 해석하였습니다.

for(int i=120;i<=1000000;i++){
    string s=to_string(i);
    int k=s.size();
    bool flag1=false,flag2=false,flag3=false;
    for(int j=0;j<k-1;j++){
      if(s[j]==s[j+1]) flag3=true;
      else if(s[j]<s[j+1]){
        if(!flag1&&!flag2) flag1=true;
        else if(flag2){
          dp[i]=0;
          flag3=true;
          break;
        } 
      }
      else if(s[j]>s[j+1]){
        if(!flag2&&flag1) flag2=true;
        else if(!flag1){
          dp[i]=0;
          flag3=true;
          break;
        } 
        else continue;
      }
    }
    if(!flag3&&flag1&&flag2) dp[i]=1;
  }

기본적으로 bool을 이용한 변수들을 이용하여서 탐색을 하였는데 flag1은 증가하는 경우에 true로 변경해 주고 flag2는 감소하는 경우에 true로 변경해 주고 마지막으로 flag3는 x가 틀린 경우에 true로 변경해 주었습니다.

젤 먼저 s [j]==s [j+1]이라면 바로 flag3을 true로 바꾸어 주었습니다.

if(s[j]==s[j+1]) flag3=true;

그다음으로 자릿수가 증가할수록 증가해야 하다가 감소해야 하기 때문에  두 가지를 조건을 이용하여서 이용하여서 결정하였습니다.

1. 만약 증가도 감소도 하지 않은 상태라면 flag2를 true로 바꾸어주고 탐색을 진행해 준다.
2. 하지만 flag2가 참, 즉 감소한 적이 있다면 flag3을 true로 바꾸어 준다.

감소하는 경우도 비슷하게 두 가지 경우로 결정하였습니다.

1. 만약 flag1이 참이고 flag2가 거짓이면 flag2를 참으로 바꾸고 탐색을 이어간다.
2. 하지만 flag1이 거짓이라면 바로 flag3을 참으로 바꾼다.

최종적으로 flag3가 거짓이고 flag1, flag2가 참이면 dp [x]를 +1 해주면 됩니다.

그 이후에는 120부터 백만까지 누적합을 이용하여서 개수를 카운팅 해주면서 모든 준비를 끝내주었습니다.

만약 [a, b]가 주어진다면 dp [b]-dp [a-1]을 정답으로 하여서 출력해 주면 됩니다.

최종 코드

#include<iostream>
using namespace std;
int n,m,t;
int dp[1000001];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>t;
  for(int i=120;i<=1000000;i++){
    string s=to_string(i);
    int k=s.size();
    bool flag1=false,flag2=false,flag3=false;
    for(int j=0;j<k-1;j++){
      if(s[j]==s[j+1]) flag3=true;
      else if(s[j]<s[j+1]){
        if(!flag1&&!flag2) flag1=true;
        else if(flag2){
          dp[i]=0;
          flag3=true;
          break;
        } 
      }
      else if(s[j]>s[j+1]){
        if(!flag2&&flag1) flag2=true;
        else if(!flag1){
          dp[i]=0;
          flag3=true;
          break;
        } 
        else continue;
      }
    }
    if(!flag3&&flag1&&flag2) dp[i]=1;
  }
  for(int i=1;i<=1000000;i++){
    dp[i]+=dp[i-1];
  }
  while(t--){
    cin>>n>>m;
    if(m<120) {
      cout<<0<<"\n";
    }
    else{
      cout<<dp[m]-dp[n-1]<<"\n";
    }
  }
}