오픈튜토리얼 문제 풀기 - 나머지 연산 및 정렬

1. 문제

[설명]

0 살 이상 99살 이하의 사람들의 나이가 주어질 때, 이를 오름차순으로 정렬하는 프로그램을 작성하라.

[입력]

입력의 첫 줄에는 테스트 케이스의 개수 T가 입력된다.

각 테스트 케이스는 한줄로 이뤄지며, 자연수  자연수 N(1 ≤ N ≤ 2, 000, 000), X1(0 ≤ X1 ≤ 99), P(1 ≤ P ≤ N)가 차례대로 입력된다.

i(i>1) 번째 사람의 나이는 xi = (xi-1*11 + 97) mod 100 이다.

[출력]

각 테스트 케이스에 대해 한줄에 오름차순으로 P번째인 사람의 나이를 출력한다.

Sample Input	Sample Output
2  5 1 5  7 9 3	85  53

원소스 : http://judge.lavida.us/problem.php?id=2103

2. 설명

단순하게 생각했는데 내부적으로 고려해야 할 사항이 많다. 나머지 연산자의 특성을 모르면 함정에 빠질 수 있다.

처음에는 P번째 값을 구하라고 해서 단순히 P번째 값만 구했는데 나머지 연산 결과에 대한 특성을 파악하지 못했다. 

3. 코드

일단 재귀 호출로 성능 무시하고 구현하면 아래와 같다. STL을 사용하여 구현을 하였다.

#include <iostream> #include <vector> #include <algorithm> int calc(int i, int p) { if(p == 1) { // return inital value return i; } else { return (calc(i, p-1) * 11 + 97) % 100; } } int calc_age(int n, int i, int p) { std::vector<int> v; for(int j = 1; j <= n; j++) { v.push_back(calc(i, j)); } std::sort(v.begin(), v.end(), std::less<int>()); return v[p-1]; } int main() { int r = calc_age(5, 1, 5); std::cout << r << std::endl; r = calc_age(7, 9, 3); std::cout << r << std::endl; return 0; }

재귀 호출 함수를 없애고 성능을 개선하는 코드로 바꾸려면 아래 코드를 쓰면 빠르지 않을까 쉽다.

int x[1000]; int calc(int i, int p) { if(p == 1) { // return inital value x[1] = i; return x[1]; } else { x[p] = (x[p-1] * 11 + 97) % 100; return x[p]; } }

4. 실행 결과

Start

85
53

Finish