gydbslove   7년 전

dp 로 접근하고 있는데 자릿수에 대한 값은 구하겠는데 그 값에 대해서 어떻게 구할지는 생각이 나지 않습니다.

대충 아래 코드로 각 자리까지의 언덕수는 구했는데 map 에 string 으로 넣어서 dp 적으로 접근해야 할까요?

sait2000   7년 전

지금 버그가 있는 거같은데 dp[0]이 내려가기만 하는 언덕수고 dp[1]이 올라갈 수도 내려갈 수도 있는 언덕수면 이렇게 고치는 게 맞을 겁니다. 8번 줄 16번 줄 고쳤습니다. 그리고 입력은 70자리(2^70 말고 10^70입니다)까지 들어올 수있으니까 int로 받으시면 안됩니다.

실제로 질문하신 부분은 어떤식으로 하시면 되냐면... 대충 이런 느낌입니다. 예를 들어 예시 입력에 있는 1234321이라 하면 1234321보다 작은 언덕수는 이런 꼴 중 하나가 됩니다.

* 6자리 이하 언덕수

* 10xxxxx, 11xxxxx

* 120xxxx, 121xxxx, 122xxxx

* 1230xxx, 1231xxx, 1232xxx, 1233xxx

...

* 123430x, 123431x

* 1234320

즉, 1의 자리부터 10^6의 자리까지 7자리중에 어디 한군데가 1234321보다 작아야 합니다. 저 각각의 경우를 dp 배열의 적당한 값들을 더해서 계산하면 됩니다.

gydbslove   7년 전

풀어보려고 노력하고 있는데 각 숫자들의 값을 걸러주는게 쉽지 않네요 ㅜㅜ

배열 인덱스 하나 추가해서 4차원 배열로 전에 어떤 숫자에서 접근햇는지 저장해서 하려고 했는데 숫자들이 썪여서 

특별한 방법이 있을까요?

댓글을 작성하려면 로그인해야 합니다.