강의자료/정보영재

2017 정보올림피아드 지역대회 고등부 50번 문제풀이

원당컴 2018. 10. 29. 10:06


문제풀이) g(0)=1,g(1)=1,g(2)=2를 반환한다고 되어 있는데...

여기서 g의 함수가 무엇을 하는지 먼저 살펴볼 필요가 있을것 같습니다.

g(11)이 들어 간다고 하면 i,j,k 가 0 부터 11까지 3중 반복이 됩니다.

그런데 어떤 경우에 f(i,j,k) 를 호출해서 r에 누적을 해서 누적한 값을 리턴하게 됩니다.

어떤 경우냐 하면 i + 2*j + 3*k == 11 인 경우에 해당합니다.

그렇다는 얘기는 다음과 같은 경우에 f(i,j,k)를 호출한다고 볼수 있겠네요.

i,j,k 는 다음과 같은 경우 호출 될것 같습니다.

 j

 k

 11

0

 0

 9

 1

 0

 7

 2

 0

 5

 3

 0

 3

 4

 0

 1

 5

 0

 8

 0

 1

 6

 1

 1

 4

 2

 1

 2 3 1
 0 4 1
 5 0 2
 3 1 2
 1 3 2
 2 0 3
 0 1 3

위와 같은 경우에 f 함수를 호출합니다.


그러면 f 함수를 확인 하면 x,y,z 중에 하나라도 음수인경우에는 0 을 리턴 x,y,z 가 모두 0 인 경우에 1을 리턴 합니다.

3차원 배열표로 그려 보면 좋을 것 같은데 3차원으로 그리기가 애매 하네요.

일단 차원을 나열해서 그려 보면 다음과 같습니다.

먼저 x=1,y=1,z=1 위치가 6 이 되는 이유는 (1,1,0) 위치와 (1,0,1) 위치 (0,1,1) 위치의 값이 합해져서 입니다.

이러한 표를 만들어 보면 k가 z 가 되므로 z 축은 3,y축은 5 까지, x축은 11까지의 그림을 그린후 각 데이터의 값을 합하면 될것 같습니다.



이런 경우 해당 위치를 먼저 마킹해 놓고 그 위치까지만 계산해 가면 훨씬 시간적인 절약이 될것입니다.


이렇게 데이터 표를 추출해 보면 다음과 같은 값을 얻을 수 있습니다.

따라서 정답은 504 입니다.


이러한 방법이 아닌 다른 방법이 있다면 살짝 힌트를 주시면 더 감사하겠습니다.


이쪽을 공부 하다 보니 한 문제를 푸는데 한가지 방법만 있는것은 아니더라구요.

요즘에 학생들에게 더 많은 경우의 수를 배우고 있기 때문에 이것이 풀어가는 한가지 방법일 뿐이라는 것을 새삼 깨닫게 되네요.

분명히 이것보다 더 좋은 방법이 있을수도 있으므로...

혹시라도 알고 계신 분은 힌트를 주신다면 다시 풀이 방법을 개선해 보도록 하겠습니다.^^


오늘도 즐거운 하루 되세요...



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






이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기