백준 2292번 파이썬
저 혼자 고민해서 풀어본 풀이방법입니다.
문제요약: 1에서부터 목적지까지의 카운트 ex) 13이 목적지라면 1->4->13 이니 카운트 3
문제풀이 사고과정:
1. 범위에 따라 카운트 수가 달라져야 한다는 것에 주목.
2. 그림을 자세히 보면 1을 둘러싼 2~7은 카운트 2, 8~19는 카운트 3, 20 ~ 37는 카운트 4가 됨.
3. 그런데 범위가 너무 많음. 범위를 일일히 if 문을 이용해서 해결하기에는 무리.
4. 그래서 이 범위를 반복문을 이용해서 만들기로 함.
5. 일단 범위의 경계값들, 예를들어 2~7의 2와 7같이 이러한 경계값들이 증가하는 규칙을 알아야 했음.
6. 즉, 2~7 -> 8~19 -> 20~37 -> 38~61에서 최소값들은 2->8 ->20->38, 최대값들은 7->19->37->61 이런식으로 증가하는데 규칙을 알아아햠.
이런식으로 해봤더니 규칙이 나옴. 다음 숫자로 넘어가기 위해 더해지는 숫자가 +6씩 커짐. 최대값 최소값 모두 똑같이
첫번째 숫자 = a1, 두번째 숫자 = a2라 가정. a2 = a1 + 6, 그다음 얘들도 똑같이 해보면 , a3 = a2 + 12, a4 = a3 +18 이런식으로 쭉쭉 가게됨. 이렇게 계속 반복되는 걸 보다보니 하나의 식으로 정리할 수 있을 것같음.
a(n+1) = a*n + 6*n 대충 이런식으로. 근데 아직 우리가 원하는 식을 만족했다기엔 아직 부족함. 해당식이 경계값을 반환하기 위해선 왠지 an = ~~~ 이런식으로 되야할 것 같음. 그래서
수열의 점화식 이용하면 an = 3*n*n - 3*n + 2 가 나옴. 7->19->37->61 이것도 똑같이 해주면 3*n*n - 3*n + 2가 도출
7. 해당식을 이용하여 코드를 짜보면