작성일 : 11-07-11 14:15
2008년도 정올 전국대회 초등부 2번/중등부 1번 기출문제
 글쓴이 : 컴스쿨(hancomedu)
조회 : 11,800  

전체적인 흐름을 정확하게 잡고 제대로 훌륭하게 작성된거 같습니다.
컴퓨터 사양이 어떻게 되는지 모르겠지만 작성하신 프로그램으로 일부 문법 수정만 해서 정올에서 채점하면 충분하게 시간내에 출력이 되고 100점을 받으실 수 있습니다.
(전국대회 채점하는 컴퓨터는 정올보다 높은 사양입니다.)

시간을 더 줄일 수 있는 방법으로는 가지치기를 하면 되는데 이 경우에는 입력된 내용을 하나씩 확인하면서 만약 현재 저장된 값이 입력된 값을 초과하는 경우 더 이상 진행하지 않고 리턴을 해주는 방법으로 하면 상당한 시간을 줄일 수 있습니다. (물론 이 문제에서는 그럴 필요가 없습니다.)

참고로 보다 실력을 키우기 위해서는 코딩 습관을 몇가지 고쳐주는게 어떨까 생각합니다.
중요한 내용을 몇가지만 말씀드리면 다음과 같습니다.

1. for문 내에 int i와 같이 변수를 선언하는 것은 컴파일러에 따라서 컴파일 에러를 발생할 수 있으므로 가능하면 별도로 선언을 하는 것이 좋을 듯 합니다.

2. 전역변수로 선언을 하면 정수의 경우 기본값이 0으로 초기화 되므로 다시 최기화하기 위한 코딩은 불필요합니다.

3. main 함수에 return 0; 이 생략되어 있군요.

4. 재귀함수에서 b의 값에 따라 동일한 호출이 여러군데 분산이 되므로 프로그램이 복잡해 보입니다. 이런때는 그냥 한가지로 호출을 한 후에 재귀함수 내에서 보정을 해주면 프로그램이 무척 심플해 질 수 있습니다.

5. 최종적으로 확인을 하는 부분에서도 동일한 문장이 여러번 반복이 됩니다. 이런 경우에도 for문을 사용하여 동일한 문장을 하나로 줄이거나, 간단하게 확인하는 함수 하나를 작성하여 호출을 하면 프로그램이 무척 간단해 집니다.

참고로 두가지 형태로 수정한 소스를 올려드리니 참고하시기 바랍니다.

for문을 이용한 코딩

#include <stdio.h>
int w[5][7][4];
int c[7][4];
int chk[5];

void world(int a, int b)
{
 int i, j, k;
 if(b>6) {
  a++;
  b=a+1;
 }
 if(a==6) {
  for(i=1;i<=4;i++) {
   if(chk[i]==1) continue;
   chk[0]=1;
   for(j=1;j<=6;j++) {
    for(k=1;k<=3;k++) {
     if(c[j][k]!=w[i][j][k]) {
      chk[0]=0;
      break;
     }
    }
    if(chk[0]==0) break;
   }
   chk[i]=chk[0];
  }
  return;
 }
 c[a][1]++;  c[b][3]++;
 world(a,b+1);
 c[a][1]--;  c[b][3]--;

 c[a][2]++; c[b][2]++;
 world(a,b+1);
 c[a][2]--;  c[b][2]--;

 c[a][3]++;  c[b][1]++;
 world(a,b+1);
 c[a][3]--;  c[b][1]--;
}

int main()
{
 int i,j,k;
 FILE*fin = fopen("INPUT.TXT","r");
 for(i=1;i<=4;i++) {
  for(j=1;j<=6;j++) {
   for(k=1;k<=3;k++) {
    fscanf(fin,"%d",&w[i][j][k]);
   }
  }
 }
 fclose(fin);
 world(1,2);
 FILE*fout=fopen("OUTPUT.TXT","w");
 fprintf(fout,"%d %d %d %d",chk[1],chk[2],chk[3],chk[4]);
 fclose(fout);
 return 0;
}

check 함수를 이용한 코딩
#include <stdio.h>
int w[5][7][4];
int c[7][4];
int chk[5];

int check(int num)
{
 int chk=0, i, j;
 for(i=1;i<=6;i++) {
  for(j=1;j<=3;j++) {
   if(c[i][j]!=w[num][i][j]) {
    return 0;
   }
  }
 }
 return 1;
}

void world(int a, int b)
{
 int i;
 if(b>6) {
  a++;
  b=a+1;
 }
 if(a==6) {
  for(i=1;i<=4;i++) {
   if(chk[i]==0) chk[i]=check(i);
  }
  return;
 }
 c[a][1]++;  c[b][3]++;
 world(a,b+1);
 c[a][1]--;  c[b][3]--;

 c[a][2]++; c[b][2]++;
 world(a,b+1);
 c[a][2]--;  c[b][2]--;

 c[a][3]++;  c[b][1]++;
 world(a,b+1);
 c[a][3]--;  c[b][1]--;
}

int main()
{
 int i,j,k;
 FILE*fin = fopen("INPUT.TXT","r");
 for(i=1;i<=4;i++) {
  for(j=1;j<=6;j++) {
   for(k=1;k<=3;k++) {
    fscanf(fin,"%d",&w[i][j][k]);
   }
  }
 }
 fclose(fin);
 world(1,2);
 FILE*fout=fopen("OUTPUT.TXT","w");
 fprintf(fout,"%d %d %d %d",chk[1],chk[2],chk[3],chk[4]);
 fclose(fout);
 return 0;
}


황희선 11-07-11 14:37
 
선생님! 정말 감사합니다!
전역변수로 하면 되는지 모르고 있었네요ㅠㅠㅠㅠ
남은 5일동안 열심히 공부해서 좋은 결과내겠습니다!
저희 컴퓨터 사양이.. 몇년 전에 산 컴퓨터이기 때문에.. 좀 안좋은 것 같네요.
정올에 가서 쓰는 컴퓨터는 사양이 좋으면 좋겠네됴^^

그런데요, 선생님 대략적으로 생각하면, 몇건을 돌리게 되면 1초가 되나요?(정올 채점용 컴퓨터에서)
저희 컴퓨터는 3천만~5천만정도 돌리면 1초가 되더라고요;;
황희선 11-07-11 14:40
 
선생님!
첫번째 코드는 약 2초정도 걸리고;;
두번째 코드는 4초정도 걸리네요;;
커트가 0.5초여서 약 4배 정도 더 걸리는데,
저희 컴퓨터가 이상한 건가요? ㅎㅎ;;
황희선 11-07-11 14:43
 
으앜ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ;;
선생님! 3번째 올리네요;;
정올에서 채첨해 보니 저희 컴퓨터보다 10배나 더 빠르네요;;
마감이 0.2초 수준;;
저희 컴퓨터가 이상한가봐요;;ㅎㅎㅎ;;
컴스쿨 11-07-11 14:53
 
1초에 얼만큼 돌릴 수 있는지는 컴퓨터의 사양이나 연산의 내용등에 따라 판이하게 달라지기 때문에 정확하게 수치화 할 수 없습니다.
다만 웬만한 연산은 1억번 이상 가능하고 간단한 연산은 그 몇배도 나올수 있으나 대략 1억번 이상의 연산이 수행되는 경우에는 시간초과에 대비할 수 있도록 코딩하는 것이 좋습니다.
 
 

Total 665
번호 제   목 글쓴이 날짜 조회
65 초등 정보올림피아드 기출문제풀이 full패키지 (1) 오미옥 03-07 9484
64 한글2010 무료강좌.... (1) 조영희 02-27 7554
63 강의신청했는데요 (1) 김연희 02-17 7230
62 강의신청했습니다. (1) 이준석 02-02 7361
61 이거 쫌 잘못된것 같은데요 (1) 이대열 01-20 7340
60 질문요 (2) 최은숙 10-22 8682
59 강의 보기가 안되네요. (2) 이수민 10-20 8448
58 결제 확인 바랍니다. (1) 김시원 09-25 8656
57 c++ Find Source please enter the path for이라는 메세지가 자… (1) 한지민 09-01 13698
56 채우기색 회색요..+차트이중축(29일오후1시시험급함 ㅜㅜ) 정동명 08-29 11165
55 올림피아드 강의 교재는 별도로 없는건지용~ (1) 한지민 08-27 9919
54 엑셀 완전초짜인데요 차트 만들기요..질문 (1) 정동명 08-25 10159
53 알고리즘 강좌 수강하고자 합니다. (1) 박수현 08-22 10366
52 알고리즘 강좌 신청합니다 (1) 이재성 07-13 8702
51 알고리즘 강의신청이요 (1) 김선미 07-13 8265
50 기하 알고리즘 강좌 질문 있습니다. (2) 황희선 07-11 9383
49 2008년도 정올 전국대회 초등부 3번문제 (1) 황희선 07-11 11026
48    2008년도 정올 전국대회 초등부 3번문제 (1) 컴스쿨 07-11 9347
47 2008년도 정올 전국대회 초등부 2번/중등부 1번 기출문제 (1) 황희선 07-10 8831
46    2008년도 정올 전국대회 초등부 2번/중등부 1번 기출문제 (4) 컴스쿨 07-11 11801
   31  32  33  34  

회사소개 | 개인정보처리방침 | 이용약관 | 찾아오시는 길 | 이메일주소 무단수집거부 | 사업자정보확인
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호 한컴에듀케이션(주) TEL : 031-388-8840 FAX : 031-388-0996
대표자 : 김동규 사업자번호 : 130-86-02870 통신판매업신고번호 : 제 2010-경기안양-888호
COPYTIGHT(C) 한컴에듀케이션(주), ALL RIGHT RESERVED.
담은강좌 : 0