BOJ 1131 숫자
문제
BOJ 1131 숫자
각 숫자 (N)에 대해 (S_K(N)) = (각 자리 숫자의 (K)제곱 합)으로 정의하고,
수열 (N, S_K(N), S_K(S_K(N)), \dots) 에서 등장하는 값들의 최솟값을 (m(N))이라 하자.
주어진 구간 ([A,B])에 대해 (\sum_{N=A}^{B} m(N)) 을 구한다.
(입력: (A,B,K), 제약: (1\le A\le B\le 1{,}000{,}000), (1\le K\le 6))
복잡도 분석
- time complexity : (제출 코드 기준) 대략 (\sum_{N=A}^{B} O(L_N \log L_N))
- (L_N) = 수열이 사이클을 만나기까지 방문한 서로 다른 값의 개수
- 각 단계마다
set삽입/탐색이 (O(\log L_N))
- space complexity : (제출 코드 기준)
best,nxt: (O(LIM))- 각
solve의set: (O(L_N))
접근법
각 수는 다음 수로 유일하게 이동한다:
[ x \to S_K(x) ] 따라서 어떤 시작점에서도 수열은 유한한 값들만 방문하다가 반드시 이전에 방문한 값으로 돌아가며(사이클) 종료 조건을 얻는다.
제출 코드는 각 시작점 (N)에 대해: 1) set으로 방문한 수를 기록하며 수열을 전개 2) 이미 방문한 값이 다시 등장하면(사이클) 종료 3) 방문했던 값 집합의 최소를 답으로 사용
또한:
nxt[x]에 (S_K(x)) 값을 캐시하여 같은 값에 대한 다음 계산을 줄임best[x]는 특정 시작점에 대한 답을 부분적으로 캐시(단, 현재 코드는best[N]만 채움)
풀이
(제출 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int A,B,K;
vector<int> best; // 한번 도달했던 숫자는 최소 결과를 저장한다.
vector<int> nxt; // 이전에 계산한 다음숫자
vector<int> min_n_res; // 여기에 저장했다가 합
int func_S_K(int N){
int c=0;
int x = N;
while (x>0){
int tmp = 1;
for(int i=0;i<K;i++){
tmp *= (x%10);
}
c += tmp;
x /= 10;
}
return c;
}
// 99 같은 숫자여도 한번 커졌다가 무조건 작아지는듯?
void solve(int N){
// N을 이용하여 수열 만들고 가장 작은숫자를 저장
// 수열이 사이클이 나오게 되나..?
set<int> s;
s.insert(N);
int t = N;
while (1)
{
// 이전에 best 저장했음
if (best[t]!=0){
s.insert(best[t]);
break;
}
int nt;
if (nxt[t]!=0){
nt = nxt[t];
} else {
nt = func_S_K(t);
nxt[t] = nt;
}
t = nt;
// 사이클 발견
if(s.find(t)!=s.end()){
break;
}
s.insert(t);
}
int min_res = *s.begin();
best[N] = min_res;
min_n_res.push_back(min_res);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>A>>B>>K;
int pow9 = 1;
for(int i=0;i<K;i++) pow9 *= 9;
ll LIM = max(B,7*pow9);
best.assign(LIM+1,0);
nxt.assign(LIM+1,0);
for(int i=A;i<B+1;i++){
solve(i);
}
cout << accumulate(min_n_res.begin(),min_n_res.end(),0LL);
return 0;
}
이전에 atcoder에서 봤던 문제와 비슷한데, 하단의 코드리뷰 내용을 정확히 이해하지는 못하고 정답은 받음.
s.insert(x)는, 결과로 {iterator - x 위치(기존에 있었거나 삽입했거나),bool - (새로 삽입 여부, 기존에 있었다면 false)}
그러므로 if(!s.insert(t).second) 이렇게 쓸수가 있다. 사이클 발견하고 그 뒤 삽입하고 할 필요없이 한번에 가능. 이미 있다면 삽입 안되니까. 이미 방문한 값 판정, 삽입시도를 한번에 함.
set 안쓰고 배열만으로 풀면 더 개선이 된다는데…
Code Review
아래는 “정답을 유지하면서” 더 안전/빠르게 만들 수 있는 개선점들이다.
1) func_S_K 상수 최적화: digitPow[10] 미리 계산
현재는 자리마다 (K)번 곱셈을 수행한다. (K\le 6), 자리수도 최대 7이라 큰 부담은 아니지만 호출 횟수가 많아지면 상수가 꽤 커진다.
개선: 0~9의 (K)제곱을 미리 계산해두면 func_S_K가 “자릿수만큼 덧셈”이 된다.
- 전처리:
digitPow[d] = d^K
- 계산:
sum += digitPow[x%10]
2) set → unordered_set(또는 배열 방문 체크)로 membership 비용 줄이기
제출 코드는 사이클 판별과 최소값 관리를 위해 set을 사용한다. 하지만 set은 균형 트리 기반이라 각 연산이 (O(\log L)).
unordered_set으로 바꾸면 평균 (O(1))로 membership 체크가 빨라질 수 있다.- 단,
unordered_set은 정렬이 없으므로*begin()이 최솟값이 아니다.- 따라서 최소값은 따로
mn = min(mn, t)로 추적해야 한다.
- 따라서 최소값은 따로
가장 작은 변경만으로 개선하려면:
set<int> s;→unordered_set<int> s;int mn = N;두고 매 스텝마다mn = min(mn, t);- 사이클 체크는
if(!s.insert(t).second) break;(find + insert 두 번 하지 않기)
3) 합계는 min_n_res에 저장하지 않고 바로 누적 가능
현재는 min_n_res에 전부 넣고 마지막에 accumulate.
- 메모리를 크게 줄이진 않지만(최대 1e6 ints ≈ 4MB)
바로ans += min_res;로 누적하면 코드도 단순해지고 벡터 push 비용도 사라진다.
4) best 캐시의 활용도가 낮음: 경로 전체에 best를 채우면 더 큰 속도 향상
현재 코드는 best[N]만 채운다. 하지만 같은 수열 “꼬리”를 공유하는 시작점이 많을 수 있어, 중간 값들에 대한 best가 비어있으면 그 구간을 다시 따라가게 된다.
더 강한 최적화(정석):
- 한 번
N에서 만든 경로(path)에 등장한 모든 노드에 대해
뒤에서부터best[노드]를 전파하여 채우면, - 다음 시작점이 중간에 이미 계산된 노드를 만나면 즉시 종료할 수 있다.
이 방식은 functional graph(각 노드 out-degree 1)에서 자주 쓰이는 최적화로, 최악 입력에서도 안정적인 성능을 기대할 수 있다.
(이 글에서는 제출 코드를 유지하기 위해 자세한 구현은 생략)
5) LIM 설정은 max(B, 7*9^K)가 적절
(N \le 1{,}000{,}000)은 최대 7자리이므로 [ S_K(N) \le 7\cdot 9^K ] 따라서 수열 전개 중 등장 가능한 값들은 0..max(B, 7*9^K) 안에서 커버할 수 있고, 배열 크기도 불필요하게 키우지 않아 메모리 면에서 유리하다.
유사 문제 추천
- Happy Number 계열(자리 제곱 합 수열) (LeetCode 202 Happy Number)
- BOJ 2331 반복수열
- BOJ 2526 싸이클
- BOJ 9466 텀 프로젝트 (functional graph)
- BOJ 13306 트리 / 오프라인 쿼리류 (캐시/전파 사고 연습용)