진짜 오랜만에 블로그 업로드^^
아니....... 진짜 다 풀어놓고 정작 핵심을 못 찾아서 계속 헤메던 문제....
나는 어떻게 풀려고 하였나
일단 보자마자 당연히 이거 수열문제구나~ 하고 감을 잡았음
그래서 항 간의 규칙을 파악하려고 노력함
그리고 나서 예를 들어서 38이라는 숫자가 있다고 치면 그 숫자랑 같이 일렬로 배열되어있는 수가 있을 거 아님? 그 수들을 찾으려고 했음
그 걸 알아야 최소 횟수로 1에 도달하는 길을 알 수 있을 거라고 생각해서... (직선이 제일 빠를 테니까)
근데 이 규칙이.... 이게 사실 내가 고등학교 때에는 이미 교육과정에서 빠진 거라 뭐 수학적으로 어떻게 표현하는 지는 모르겠는데^^ 좀 골때림
그냥 같은 숫자로 해서 쭉 올라가는 게 아니라 6 12 18 24 이 간격으로 해서 줄마다 숫자가 더 붙음
그래서 어떤 줄은 커지는 간격이 4 10 16 22 이러고 어디는 5 11 17 23 이러는 거임!!
여기서 이거 이대로 가면 안 되겠다는 걸 느낌 저걸 다 구할 방법을 배운 적도 없고 방법이 딱히 떠오르지도 않아서...
어떻게 풀었어야 하였나
핵심은....
1. 벌집 모양, 즉 원의 형태로 빙 둘러 있고 1은 그 중심에 있음.
2. 직선으로 가는 것은 최단 거리와 아무런 상관이 없음!!!
이거였다.
따라서 구체적으로 '최단 거리'로 도착하기 위해 그 경로가 어떻게 되어야 하는지~를 생각할 게 아니라 그냥 어차피! 한 층에! 한 칸을 반드시 지나게 되고! (한 층에 두 칸 이렇게 가는 건 당연히 최단 거리가 아니게 되니까 애초에 고려할 필요가 X) 그리고 1이 가운데에 있기 때문에 그냥 한 층에 한 칸 지나는 식으로 가면 어디서 출발하든 반드시 1에 도착하게 됨. 따라서 경로가 문제가 아니라 그 숫자가 몇 층에 있는지가 핵심이었던 거!!!!
그러면 사실... 이미 층수별 규칙은 진작에 찾아둔 상태였기 때문에 문제가 너무 쉬워진다.
코드를 뚝딱 짜보면 다음과 같음. (C)
#include <stdio.h>
int main() {
int N, i = 1, cnt=0;
scanf("%d", &N);
N-=1;
cnt++;
while (N>0) {
N-=6*(i++);
cnt++;
}
printf("%d", cnt);
}이 와중에 while에서 N>1이라고 했다가 진짜 N=1 돼서 한 번 더 빼줘야 되는데 안빠져가지고 틀렸던 건 안비밀^^... 범위 조심해야지
뭐... 일단은 시간제한도 넉넉하니까 숫자 빼가면서 하는 풀이가 제일 간단하고 또 문제 낸 사람도 그걸 의도했을 거라고 생각했고
숫자를 6 - 12 - 18 이런 식으로 뺄 꺼니까 i 하나 주고 늘려가면서 돌리고
또 1일 때 예외처리 한 사람들도 있던데 난 그러기 싫어서... 먼저 1 빼버리고 아예 0보다 작으면 반복 못 들어가게 막아버렸음 그럼 예외처리 안 해도 답 똑같이 나오니까?
간결하고 만족스러운 풀이인 듯 하다
왜 그렇게 풀려고 하였나
이건 진짜 아무리 생각해도 주입식 교육의 폐해임ㅋㅋㅋㅋㅋㅋㅋ
원래 고등학교 수준에서 나오는 '최단 거리를 구하세요' 문제는 이런 어디로 가든 일단 무조건 정답!!! 이런 느낌이 아님
정말 그 이상적인 경로를 삭 거쳐야만 최단 거리가 나오고 따라서 문제는 그 경로를 찾는 것을 의도하는 문제랄까..?? 그래서 자연스럽게 여기서도 그 '경로'를 구해야 한다고 자연스럽게 생각하게 된 것 같음 (근데 사실 이것도 그 경로가 직선이 아니더라도 괜찮다는 걸 금방 눈치챘어야 됐는데... 결국 나의 잘못이다)
또 수학적 귀납법 문제들도 이런 뭐라하지?? 이런 수열을 딱 다루는 건 아닌데 은근 문제에 나오기는 해가지고 이걸 과감하게 끊어낼 생각을 못한 거 같음 뭐 풀 수 있으니까 줬겠지 근데 나는 못 풀겠네..^^ 이런 느낌ㅋㅋㅋ
결론
아무튼 무슨 문제든 직관 쓰는 거 좋긴 한데 그보다는 먼저 문제의 본질이 뭔지를 먼저 파악하려는 습관을 길러야겠음^^ 재밌었다!
