카테고리 없음
[2주차] 알고리즘 과제
jwk818
2023. 4. 5. 16:04
<백준 1038번>
https://www.acmicpc.net/problem/1038
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
n번째 감소하는 수를 구하는 문제였다. 모든 숫자를 확인하기에는 시간이 많이 걸릴 것이라고 생각했다.
0부터 9까지는 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]로 10부터 99까지는 [10, 20, 21, 30, 31, 32...] 순서로 진행된다.
#include <stdio.h>
#include <math.h>
int main(){
int n;
scanf("%d", &n);
long long num[10000]; // 감소하는 수를 저장하는 배열
int first, last; // 한자리 아래의 감소하는 수의 범위를 나타낸다.
int cur; // 다음 나오는 감소하는 수를 넣을 위치
for(int i = 0; i < 10; i++) // 0~9번째까지는 그대로 0~9를 넣는다.
num[i] = i;
first = 0; // 한자리 숫자들은 0부터
last = 9; // 9까지 들어가 있다.
cur = 10; // 0~9까지 넣었으므로 다음 위치는 10
for(int i = 1; i < 10; i++){ // 10의 몇승인지를 나타낸다. ex) i가 2이면, 10의 2승인 백 대 수들 = 세자리 수들
for(int j = i; j < 10; j++){ // j는 현재 수의 맨 앞자리 숫자를 의미한다. ex) j가 3이면, 3xx
for(int k = first; k <= last; k++){ // 한자리 아래의 감소하는 수들을 확인해서 ex) 두자리 수 중 감소하는 수 = 10, 20, 21, 30, 31 등
if(num[k] / pow(10.0, i-1) < j){ // 해당 수의 맨 앞자리 숫자가 j보다 작다면 ex) 위의 숫자 중 10, 20, 21만 해당한다.
num[cur++] = j * pow(10.0, i) + num[k]; // 해당 감소하는 수의 맨 앞에 j를 추가했을 때 감소하는 수가 된다. 그러므로 감소하는 수 배열에 추가 ex) 310, 320, 321 추가
if(cur > n){ // n번째 감소하는 수를 찾았다면
printf("%lld\n", num[n]); // n번째 감소하는 수 출력
return 0;
}
}
}
}
first = last + 1; // 한자리 위의 감소하는 수 중에 첫번째를 가르킴
last = cur - 1; // 한자리 위의 감소하는 수 중에 마지막을 가르킴
}
printf("-1\n"); // n번째 감소하는 수가 없으므로 -1 출력
return 0;
}0부터 9까지는 이해가 되는데, 두자릿수, 세자리수는 어떻게 해결해야할지 모르겠어 코드를 참고했다. 아직 코드를 직접 짜는 것이 서툴러 시간이 더 필요할 것 같다.
[참고]
https://terry1213.github.io/backjoon/1038/
[백준 1038번] 감소하는 수
문제 설명
terry1213.github.io
<백준 11659번>
https://www.acmicpc.net/problem/11659
슬라이딩 윈도우 기법을 사용하여 배열에 누적합을 저장하고, 만약 구간이 2 4 라면 arr[4]-arr[2]를 구해주는 식으로 구간합을 구할 수 있다. 숫자 n과 m을 입력 받고 arr[b] - arr[a-1]을 출력하면 a부터 b까지의 누적합을 구할 수 있다.
[참고]