2017년 정보올림피아드 전국본선문제 초2번 중1번 방배정하기

이제 2018년도 정보올림피아드 예선 준비 할 수 있는 기간이 3달 정도 밖에 안남았네요.^^

학생들에게 별로 남은 시간이 많지 않다는 이야기를 해 주는데...

학생들은 항상 느긋하기만 하네요...^^

전국대회 진출을 하기 위해서는 저희 같은 경우는 인천시에서 11등 안에 들어야 전국대회를 나가는데 말이죠...

그런데 저희 원에서 준비하는 학생들 전원이 진출을 했으면 하는 바램도 가져 보지만...

저희 같이 오픈한지 몇개월 되지 않은 곳에서 3-4명의 티켓을 가져 온다고 하는것은 정말 너무 많은 욕심을 부리는 것 같아...

내심 제 마음만 조마조마 해지네요.^^

알고리즘이란게 정보올림피아드 대회만을 목적으로 배우는 것은 아니지만...

아무래도 학생들이 어떤 성과물이라도 나타난다면 그보다 더욱 더 흥미 진진한 이야기는 없을것 같다는 생각이 들어서...

내심 정보올림피아드 준비를 하고 있는 모든 학생들이 전국대회에 진출해서 한번 겨뤄 봤으면 하는 마음이 가득하네요.^^

오늘은 2018년도 정보올림피아드 예선 대비 하여 

전년도 전국대회 문제가 한문제는 꼭 나오는 것을 확인 하여...

2017년도 정보올림피아드 전국본선 초등 2번 방배정하기 문제를 풀어 보겠습니다.

2017년도 정보올림피아드 전국본선 초등 1번 딱지문제 풀이는 다음을 참고 하시면 됩니다. - http://wondangcom.com/119?category=717978 

3073 : 방 배정하기 제한시간: 1Sec    메모리제한: 32mb 해결횟수: 40회    시도횟수: 82회    정보 초등학교 6학년 여학생들(중학교 3학년 남학생들)은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.   예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.   방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오.   단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.     표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다. 빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다. 부분문제의 제약 조건 ● 부분문제 1: 전체 점수 100점 중 3점에 해당하며 입력 예시로 주어진 입력만 존재한다. ● 부분문제 2: 전체 점수 100점 중 5점에 해당하며 A=1이다. ● 부분문제 3: 전체 점수 100점 중 14점에 해당하며 B, C는 A의 배수이다. ● 부분문제 4: 전체 점수 100점 중 78점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.  [Copy] 5 9 12 113  [Copy] 1  [Copy] 3 6 9 112  [Copy] 0

저는 다음과 같이 풀었습니다.

가장 기본적인 방법인 백트래킹 방법으로 풀었는데요...

혹시라도 타임아웃이 걸릴까 해서 동적테이블 dp 테이블 만들어서 한번 계산했던 부분은 다시 계산 하지 않도록 하여 계산 속도를 높였습니다.

이러한 백트래킹이 아니라도 다른 방법도 많기 때문에 예선 문제에는 이와 같은 기법으로 문제가 나올 확률은 없겠네요.

하지만 이러한 문제를 풀어 봄으로써 알고리즘을 한번 생각해 보면 예선에 이문제가 출제되는 경우라면 어떤식으로 출제 되어도 문제없이 답안을 찾아 낼것입니다.

일단 방의 인원을 room 에 입력을 받았고요. 현재 총 학생수를 tot 에 입력을 받았습니다.

그리고 나서 한개의 방에 모두 들어갈수 있다면 1을 리턴 하고 모두 들어 갈 수 없다면 그 방의 인원수 만큼 배정후에 다시 똑같은 루틴을 태우면서 두번째 방 세번째 방에 똑같은 방식으로 배정을 해 보도록 프로그래밍을 구현해 보았습니다.

소스는 아래를 참고 하시면 될것 같네요.

#include <iostream> #include <stdio.h> #include <string.h>   using namespace std; int room[3],tot; int dp[301];   int roomcheck(int cnt) {     if (cnt < 0) return 0;     if(dp[cnt]!=-1) return dp[cnt];     for(int i=0;i<3;i++) //각 방에 사람을 배정 해 보     {         if(cnt % room[i] == 0) return dp[cnt] = 1; //방을 배정할 수 있다         if((cnt-room[i]) < 0 ) continue;         dp[cnt-room[i]] = roomcheck(cnt-room[i]); //해당방에 인원을 배정 후 다음 방을 배정 해 보자.         if(dp[cnt-room[i]]) return dp[cnt-room[i]];     }     return 0; //여기까지 온것은 배정 할 수 없는 경우이다. }   int main() {     //freopen("input.txt","r",stdin);     scanf("%d %d %d %d",&room[0],&room[1],&room[2],&tot);     memset(dp,-1,sizeof(dp));     printf("%d",roomcheck(tot));     return 0; }

정보올림피아드 준비하는 모든 학생들이 좋은 결과를 공유해 보기를 기대합니다.

정보올림피아드 문제 풀이 리스트 정리