정보올림피아드 초등 - 지역예선] 2008년도 33번문제

문제

정보초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

(규칙 1) 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.

(규칙 2) 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.

(규칙 3) 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다.

이 때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 게시된 지 가장 오래된 사진을 삭제한다.

(규칙 4) 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.

(규칙 5) 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 사진틀의 개수를 나타내는 자연수가 주어진다. 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸 하나를 사이에 두고 추천받은 순서대로 주어진다. 단, 사진틀의 개수는 20개 이하이고, 총 추천 횟수는 1000번 이하이다. 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

 

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 사진틀에 사진이 게재된 최종 후보의 학생 번호를 빈 칸을 사이에 두고 출력한다. 단, 출력순서는 상관없다.

입력과 출력의 예

입력(INPUT.TXT)

3 9 2 1 4 3 5 6 2 7 2

출력(OUTPUT.TXT)

2 7 6

 

 

33. ㉠에 들어갈 내용은 무엇인가?

①m = 0

②m < n

③m <= n

④m >= n

⑤m > n

34. ㉡에 들어갈 내용은 무엇인가?

①time(j) = 0

②time(j) = 1

③time(j) = i

④time(j) = time(j - 1) + 1

⑤time(j) = time(m) + 1

35. 위 프로그램에서 m = m + 1 이 들어가야 할 곳은?

①(a)

②(b)

③(c)

④(d)

⑤(e)

 

문제풀이) 프로그램의 알고리즘을 따라가 보면 다음과 같다.

n <-- 앨범 갯수

k  <-- 추천 횟수

student <-- 학생 추천번호

voite <-- 학생 번호 투표 횟수

time  <-- 학생 추천 받은 시간

처음 for 문으로 추천 횟수 만큼 루프를 돌면서 추천 번호를 입력 받아 비교 한다.

알고리즘으로는

우선 입력 받은 추천 번호를

기존 앨범에 존재하는 지 확인 하여 앨범에 존재 하면 투표의 횟수를 증가 시킨다. (1) 번 위치

만약 없으면 현재 등록 count(m) 이 앨범 갯수(n) 보다 작으면  앨범에 추가 시킨 후 등록 앨범 count(m) 을 증가 시킨다.(j->현재 앨범위치)  (2) 번 위치

만약 현재 등록 cont(m) 이 앨범 갯수(n) 보다 크면 현재 등록 되어 있는 앨범의 추천수(vote) 를 비교 하여 vote 가 작으면 그 위치의 student 에 추천번호를 입력 하며 voite 를 셋팅한다. time 은 현재 진행 시간을 입력 한다. (3) (4) 번 위치

예제에서 처럼 2,1,4,3,5,6,2,7,2 가 순서 대로 입력 되는 경우

다음과 같은 로직을 타게 된다.

처음 2 가 입력 된 경우

m 이 0 이므로 (1)은 타지 않고

바로 (2) 번 프로세스를 타게 된다. 이때 ㉠ 은 m < n 이 된다. m 이 0 부터 시작 되므로 3보다 작아야 0,1,2 의 3개 가 되므로

(2)번 프로세스에서 j = 0 값을 가지고 빠져 나오면서 m 의 값을 하나 증가 시켜서 m = 1이 된다.

(4)번 프로세스에서 student[0] = 2,vote[0] = 1,time[0] = 0 이 된다.

여기서 time[j] = i 가 되어야 하는 이유는 진행 시간의 순서를 기록하는 변수이므로 순차적으로 증가 시켜 줘야 한다.

이와 같이 1,4 역시 동일한 루틴을 타면

(2)번 프로세스에서 j의 값이 1 과 2로 각각 설정 되며

(4)번 프로세스에서 student[1] = 1,vote[1]=1,time[1]=1

student[2] = 4,vote[2]=1,time[2]=2 가 된다.

다음으로 3 이 입력 된 경우

현재 등록된 앨범에 없으므로 (1)번 프로세스는 타지 않으며

 현재 m의 값이 3 이므로 (3)번 프로세스를 타게 된다.

t의 값이 1 ~ 2 로 변하면서 vote[0] 과 비교 하면서 추천수를 비교 후 같으므로 time 을 비교 해서 time[0] 이 time[1],time[2] 보다 작으므로 j = 0 값이 된다.

따라서 (4)번 프로세스에서 student[0] = 3,vote[0] = 1,time[0] = 3 이 되며

5,6 이 차례대로 입력 되는 경우

(3)번 프로세스에서 vote의 값이 같으므로 time 을 비교해서 각각 j 값을 1,2 로 셋팅 되어져 나오면서

(4)번 프로세스에서 student[1] = 5, vote[1] = 1, time[1] = 4

                            student[2] = 6,vote[2]=1,time[2] = 5 가 되며

다음으로 2,7 이 입력 되는 경우 똑같은 루틴을 타게 되면

(3)번 프로세스에서 time 에 의해 j는 0,1 을 가지고 나오게 되며

student[0] = 2,vote[0] = 1,time[0] = 6

student[1] = 7, vote[1] = 1, time[1] = 7

마지막으로 2 가 입력 되면 (1)번 루틴에서 j의 값이 0 인경우 2를 찾아서 vote[0] = 2 로 증가 시킨후

printf 문을 통해 숫자를 출력 한다.

마지막 까지 수행해 보면

student[0] = 2,vote[0] = 2,time[0] = 6

student[1] = 7,vote[1]=1,time[1] = 7

student[2] = 6,vote[2] = 1,time[1] = 5

의 값을 갖게 된다.

이 프로그램에서 약간 보완을 한다면 (1)번 과정에서 time 값을 셋팅 해주는것이 맞음

정답)

33번) 2번 ( m 이 0 부터 시작 하므로 n보다 작아야 됨)

34번) 3번 ( 시간이 지나는 것을 표시하기 위함이므로 증가 시켜야 됨

35번) 2번 (일반적으로 증가 시키는 문장을 찾을때 사용 후에 증가 시킴 하지만 알고리즘을 꼭 파악해야 됨 여기서 m은 현재 등록되어 있는 앨범의 갯수이므로 (b) 의 위치에서 증가 시켜야 함