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

문제풀이) 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 는 다음과 같은 경우 호출 될것 같습니다.

i	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 입니다.

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

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

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

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

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

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

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