[삼성 SDS 알고리즘 사전테스트] 쉬어가는 페이지

[삼성 SDS 알고리즘] 쉬어가는 페이지

지난 일요일 사전테스트가 종료되었습니다. 테스트기간동안 푼 문제 해결방법을 포스팅하려고 합니다.

문제 출처 : https://koitp.org/problem/SDS_TEST_PAGE/read/

문제

수진이는 기말고사를 앞두고 시험 공부를 하고 있었다. 그런데 공부해야 하는 참고서의 두께가 너무 두꺼워 참고서의 모든 페이지를 볼 엄두가 나지 않았다. 참고서 전체가 모두 시험범위이었기 때문에 수진이는 범위 전체를 공부하는 것을 포기하고 특정 페이지만 골라 띄엄띄엄 보기로 했다.

띄엄띄엄 보는 방법은 다음과 같다. 우선 시작할 페이지 S 와 건너 뛸 페이지의 수 J 를 정한다. 그런 다음, S 페이지를 보고 J 페이지만큼 건너 뛴 다음 페이지를 보고, 또 J 페이지만큼 건너 뛴 페이지를 보는 방법으로 공부를 하기로 했다.

예를 들어 S = 23 이고 J = 3 이라면 일단 23 페이지를 보고 3 페이지만큼(24, 25, 26페이지) 건너뛴 다음 27 페이지를 보고, 그 다음 31 페이지, 그 다음 35 페이지 .. 이렇게 보며 공부를 하게 될 것이다. 물론 J = 0 이라면 건너뛰는 페이지가 없으므로, 시작 페이지부터 참고서의 끝까지 꼼꼼히 보게 될 것이다.

그런데 다행스럽게도 참고서의 어떤 페이지들은 공부해야 할 지루한 내용 대신 머리를 식히는 쉬어가는 페이지로 구성이 되어 있다고 한다. 수진이가 공부를 하다가 쉬어가는 페이지를 보게 되면 공부를 하느라 초조한 마음을 조금이나마 달랠 수 있을 것이다.

참고서의 전체 페이지 수 N 과 수진이가 정한 S 와 J 의 값, 그리고 쉬어가는 페이지의 수와 그 정보가 주어졌을 때 수진이가 자신의 방식대로 참고서를 볼 경우 쉬어가는 페이지를 보게 되는 횟수를 계산하는 프로그램을 작성하여 보자.

[제한조건]

1. 참고서의 전체 페이지의 수 N 은 10 이상 10000 이하의 정수이다.
2. 참고서는 중간에 찢어진 페이지가 없으므로 1페이지부터 N페이지까지 모두 존재한다고 한다.
3. 수진이가 볼 시작페이지 S의 값은 1 이상 N 이하의 정수이다.
4. 건너뛰는 페이지의 양 J의 값은 0 이상 10000 이하의 정수이다.
5. 쉬어가는 페이지의 개수 K의 값은 1 이상 1000 이하의 정수이다.

입력

첫 줄에 테스트 케이스의 수 T(<=50) 가 주어지며, 그 다음 T 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 구성되어 있으며, 첫 줄에 참고서의 페이지 수 N, 수진이가 볼 시작페이지 S, 건너뛸 페이지의 양 J, 참고서 내에 쉬어가는 페이지의 개수 K 가 공백으로 구분되어 차례대로 주어진다. 그 다음 줄에는 쉬어가는 페이지의 정보(몇 페이지가 쉬어가는 페이지인지)를 나타내는 서로 다른 K 개의 정수가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 #x (x는 테스트 케이스 번호, 1부터 시작) 을 출력하고 공백을 하나 둔 후, 수진이가 공부하면서 보게 될 쉬어가는 페이지의 총 개수를 출력한다.

힌트

(입력)
3
40 2 2 7
5 10 15 20 25 30 35
50 23 3 2
43 39
100 35 1 10
10 9 8 7 6 5 4 1 2 3

(출력)
#1 3
#2 2
#3 0

계획 및 분석

총 전체 페이지가 최대 10000쪽까지 가능하므로, 배열을 10001개로 만들어 생성해야겠다고 생각했습니다. 

이때 페이지 수, 시작 페이지, 건너뛰는 페이지 수, 쉬는 페이지를 각각 입력하게 되는데, 테스트케이스마다 따로 저장하기 위해 모두 배열로 선언하고 시작했습니다. 배열의 수는 제한조건에 맞춰서 조금 여유롭게 만들었습니다.

int T, N[10001], S[10001], J[10001], K[1010];

int rest[1010];

int count[1010] = { 0 };

count 배열은, 쉬어가는 페이지의 수를 저장할 곳으로 만들었습니다.

테스트케이스로 입력한 수만큼 for문을 돌려 반복시키고, 시작 페이지가 페이지 수보다 작은 동안 쉬어가는 페이지와 일치할 때마다 count를 증가시키며 저장하게 되었습니다. 건너뛰는 수는 J[i] 배열이므로, 한번 while문이 진행되면 시작 페이지 배열에 해당하는 S[i]를 증가시키는 방법을 이용했습니다. 

전체 소스 코드

#include <iostream>
 
using namespace std;
 
int main() {
    int T, N[10001], S[10001], J[10001], K[1010];
    
    int rest[1010];
    int count[1010] = { 0 };
 
    cin >> T; // testcase
 
    for (int i = 1; i <= T; i++) {
        cin >> N[i] >> S[i] >> J[i] >> K[i]; // 페이지 수, 시작, 건너뜀, 쉼
 
        for (int j = 1; j <= K[i]; j++) {
            cin >> rest[j];
        }
 
        int allBook = N[i];
        int startBook = S[i];
 
        while (S[i] <= N[i]) {
            
            for (int z = 1; z <= K[i]; z++) {
                if (S[i] == rest[z])
                    count[i] += 1;
            }
            S[i] += (J[i] + 1);
        }
    }
 
    for (int q = 1; q <= T; q++) {
        cout << "#" << q << " " << count[q] << endl;
    }
 
}