[백준 알고리즘] 24268번 : 2022는 무엇이 특별할까?

https://www.acmicpc.net/problem/24268

24268번: 2022는 무엇이 특별할까?

c++로 백준 24268번 문제를 풀어보겠다.

 

 

 

 

 

문제

백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다.

그렇다. 2022$2022$를 5$5$진법으로 표현하면 31042(5)${31042}_{(5)}$로, 5$5$진법의 각 숫자인 0$0$, 1$1$, 2$2$, 3$3$, 4$4$가 모두 한 번씩 나타난다. 다음에 이런 년도가 오려면 2054년이 되어야 한다.

수 N$N$과 진법 d$d$가 주어진다. 당신은 수 N$N$보다 크면서, d$d$진법으로 표현했을 때 d$d$진법의 숫자가 모두 정확히 한 번씩 등장하는 가장 작은 수를 찾아야 한다. 단, 수를 표기할 때는 앞에 불필요한 0이 존재해서는 안 된다.

입력

첫 번째 줄에 수 N$N$과 진법 d$d$가 공백을 사이에 두고 10$10$진법으로 주어진다.

출력

첫 번째 줄에 N$N$보다 크면서 d$d$진법으로 표현했을 때 d$d$진법의 숫자가 모두 정확히 한 번씩 등장하는 수 중 가장 작은 것을 10$10$진법으로 출력한다.

만약 그런 수가 존재하지 않는다면, 첫 번째 줄에 −1$-1$을 대신 출력한다.

제한

•  1≤N≤109$1 \le N \le 10^9$ 
•  2≤d≤9$2 \le d \le 9$ 
• 입력으로 주어지는 모든 수는 정수이고, 10$10$진법으로 표현되어 있다.

예제 입력 1 복사

2021 5

예제 출력 1 복사

2022

 

 

 

 

<문제 풀이>

 

 

내가 작성한 코드는 다음과 같다.

 

여러번 시도했지만, 백준 사이트에서는 '시간 초과'라고 떴다.

입력받은 수 N을 d진법으로 바꾸는 단계까지는 성공했지만, 그 다음 단계인 'd진법의 숫자가 모두 정확히 한 번씩 등장하는 수 중 가장 작은 것'을 구하는 것은 성공시키지 못했다.

 

이외에도 알고리즘이 너무 복잡해서 생기는 문제도 있을 것이다. 다음에 다시 도전해봐야겠다.