[백준]1669 멍멍이 쓰다듬기

문제소개

---

1669 멍멍이 쓰다듬기는 수학 문제입니다. 

계산 과정에서 2,147,483,648만큼 큰 값이 나올 수 있으므로 유의하면서 풀면 될 것 같습니다.

 

문제해결

---

원숭이와 멍멍이는 운명의 라이벌입니다.

원숭이가 멍멍이 머리를 쓰담쓰담하고 싶은데 키가 작아서 매일 주문을 외웁니다.

주문 덕분에 원숭이는 하루에 키의 양을 1cm 늘릴 수 있습니다.

예를 들어 어제 4cm 컸으면 오늘은 3cm, 4cm, 5cm 중에 하나만큼 키를 늘릴 수 있습니다.

 

계속 키를 늘리면 좋겠지만 원숭이의 키는 시작 날과 끝 날에 무조건 1cm만 늘릴 수 있습니다.

예를 들어 8cm 커야한다면 아래와 같이 최소 5일이 걸리겠습니다.

 

1일	2일	3일	4일	5일
1cm	2cm	2cm	2cm	1cm

 

	1일	2일	3일	4일	5일	6일	7일
3cm	1	1	1
4cm	1	2	1
5cm	1	2	1	1
6cm	1	2	2	1
7cm	1	2	2	1	1
8cm	1	2	2	2	1
9cm	1	2	3	2	1
10cm	1	2	3	2	1	1

 

규칙을 찾기 위해서 표로 정리해보았습니다. 

짐작하시겠지만 최소의 일수로 키를 늘릴려면 ^ (꼬깔콘) 모양이 가장 이상적일 것 입니다.

그렇게 되는 경우를 찾아보면 1, 4, 9, 16, 25 ... N^2인 것을 알 수 있습니다.

또한, 2 X N - 1 일이 걸린다는 것도 알 수 있습니다.

그러므로 8cm만큼 크기 위해서 걸리는 최소 일수는 (2 X 2 - 1)와 (2 X 3 -1) 사이 입니다.

 

정리하면

1) N^2 일 때가 가장 이상적이다.

2) N^2 일 때의 최소 일 수는 2 X N - 1일이다.

3) 1cm, -1cm의 증가폭이며 시작과 끝은 무조건 1cm만 증가할 수 있으므로 대칭적이다.

위의 3가지 규칙을 이용하면 쉽게 답을 찾을 수 있습니다.

 

소스보기