[BOJ] 줄어드는 수 1174번 C++

2024. 6. 9. 15:24· Algorithm

 

 

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

 

접근 방식

 

먼저 줄어드는 수를 만들수 있는 모든 가짓수를 만든다

이때 만들수 있는 최대 줄어드는 수는 987,654,321이기 때문에 2초안에 가능하다

 

만든 수를 모두 정렬하고 만약 만든 모든 수의 개수가 N보다 작다면 N-1인덱스의 값을 출력하고 크다면 -1을 출력하면 된다!

 

처음에는 잘 이해가 가지 않았는데 두번 세번 다시 생각해보니 조금 이해가 되었다..!

 

 

코드

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> v;

void sol(ll num, int last) {

    for(int i=0; i<last; i++) {
        ll new_num = num * 10 + i;
        v.push_back(new_num);
        sol(new_num, i);
    }


}

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

    for(int i=0; i<10; i++) {
        v.push_back(i);
        sol(i, i);
    }

    sort(v.begin(), v.end());

    if(N <= v.size()) cout<<v[N-1];
    else cout<<-1;
}

'Algorithm' 카테고리의 다른 글

[BOJ] 애너그램 6443번 C++  (1) 2024.06.10
[BOJ] 선발 명단 3980번 C++  (1) 2024.06.10
[BOJ] 계란으로 계란치기 16987번 C++  (1) 2024.06.08
[BOJ] 연산자 끼워넣기 14888번 C++  (1) 2024.06.06
[BOJ] 외판원 순회 2 10971번 C++  (0) 2024.06.06
'Algorithm' 카테고리의 다른 글
  • [BOJ] 애너그램 6443번 C++
  • [BOJ] 선발 명단 3980번 C++
  • [BOJ] 계란으로 계란치기 16987번 C++
  • [BOJ] 연산자 끼워넣기 14888번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 그리디
  • dp
  • TOPCIT
  • 스택
  • BFS
  • 백트래킹
  • C++
  • BOJ
  • 탐욕 알고리즘
  • 알고리즘
  • 우선순위 큐
  • javascript
  • 완전탐색
  • 리액트
  • Greedy
  • 모던 자바스크립트 딥다이브
  • 자료구조
  • 데이터베이스
  • 문자열
  • 그래프 탐색
  • 누적합
  • Stack
  • react
  • 모던 리액트 딥다이브
  • 투 포인터
  • typescript
  • Fe
  • CS
  • 백준
  • 자바스크립트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 줄어드는 수 1174번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.