오일러 15번

단순한 dynamic pr 문제라고 생각했는데, 수학적인 지식을 요구하는 문제였다(euler 문제들이 전부 그렇지만!)

또 조합으로도 풀 수 있는 문제이다.

dynamic 문제 유형과 유사하여 기억을 되살려 풀려고 했지만 실빼..

검색을 해보면서 다른 분들은 어떻게 풀었는지 참고를 하였다.

그 중 dynamic 으로 푼 블로거 분이 계셔서 이를 참조하였는데 정답이 long long int로 꽤 큰 값이 나왔음에도 빠른 시간안에 수행이 되었다. 이 후 코드리뷰를 진행하는데,

for (int i = 0; i < N+1; i++) {
		arr[N][i] = 1;
		arr[i][N] = 1;
	}

위 부분이 이해가 되지 않았다..검색을 좀 더 해보니 아래 블로그가 top으로 떠 참고를 해보았다 아래 블로그가 원본 코드를 가진 곳인듯 했다(영어였음,,이해하는데 시간 더 걸렸음)

https://www.mathblog.dk/project-euler-15/

해당 작업을 해준 것은 목표을 가기 위해 거치는 장소가 정해져 있기 때문이라는 것을 알 수 있었다. 즉,

과 같이 목표지점인 오른쪽 아래로 가기 위해선 무조건 위(top) 방향 점에서든, 왼쪽(left) 방향 점에서 부터 온다.

그럼 해당 부분들은 1로 미리 표기할 수 있다. 나아가 이들 점들이 확대되어 오는 방향의 점도 1로 표기할 수 있다.

이쯤되면 숫자가 의미하는 게 정확히 무슨 뜻인지 저 점들이 왜 1로 표기되는지 정확히 이해가 안되었다..

잘 생각해보니 숫자들이 의미하는 건 다른 지점으로 갈 수 있는 정도이다. 그래서 아래 그림처럼

초록색으로 표기된 숫자 2는 앞서 말한 1들로 나아갈 수 있다(목표지점의 위, 왼쪽 방향에 있던 점들) 그 때 점들의 값이 1이므로 1+1 = 2가 되고

파란색으로 표기된 숫자 3의 경우 오른쪽과 아래 방향으로 가게 되는데 해당 방향의 숫자들이 2와 1이므로 1+2 = 3 이 되는 것이다.

앞서 말한 목표지점에서 부터 왼쪽 방향, 위쪽 방향으로 떨어진 점들이 목표로 가는 건 하나의 길(1) 뿐이다. 그래서 위에 표기될 때 1로 표기된 것이고 다른 것들도 마찬가지로 그런 방식으로 표기되었다.

혹시 오른쪽 방향과 아래쪽 방향으로만 가게 된다면 1+1 = 2 라서 2가 나와야 맞지 않느냐고 하면..나도 모르겠다..수학적 개념이 부족한 상태에서 이해한 것이라 혹 다른 분들이 보시면 피드백 해주셔서 도와주시면 좋겠다.

한 부분을 이해하기 위해서 멀리왔다..

그런 이유로 경계부분들을 1로 미리 표기한 것이고 다른 부분은 dynamic prg 로 구현하여 해결할 수 있었다.