리유나의 항해일지

안녕하세요. 리유나입니다. 생각해보니 ICPC에서 J번을 그럭저럭 괜찮은 페이스로 자력 해결을 했는데, 그보다 훨씬 쉬우면서 비슷한 로직을 가진 1081번 합.이라는 문제가 있었고 제가 이걸 6년 전, PS에 거의 처음 입문했을 때 시도했다가 틀린뒤로 건드리지도 않았다는 사실을 깨달았습니다. https://www.acmicpc.net/problem/1081 1081번: 합 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 한번의 구현 실수를 제외하면, 아주 손쉽게 풀리는 스타일이었지만, 처음 입문하시는 분들이라면 다들 고등학교 시절의 저처럼 무언가 실수를 하실 부분이 있을듯 하니 도움이 되었으면 하는 바람에 포스팅을 시작합니다..

리유나입니다. ICPC에서 제가 풀었던 문제의 풀이를 조금 더 자세히 적어보려고 합니다. 대략적인 풀이의 스케치는 이 글의 아랫부분에 있습니다. 수학문제와 dp문제의 경계 어딘가쯤에 있는 Digit DP라는 스타일의 문제이고, 사실 저는 수학이라고 생각하고 접근했다가 '에이 수학 아니잖아... 하지만 풀이는 나왔으니 뭐 풀어야지'하고 풀었습니다.(Digit DP라는 말이 있는 걸 대회 후에 처음 알았습니다.)한국 리저널에는 잘 안나오던 스타일의 문제인 듯한데, 제게는 찐수학만큼은 아니지만 상당히 강한 유형이었기 때문에 그리 어렵지 않게 풀었습니다....였으면 얼마나 좋았을까요? 예외처리 하느라 고생하면서 조금 어렵게 풀었습니다. 문제를 해석하면, L부터 R까지의 자연수 중에서 모든 자릿수를 곱했을 때 k..

문제는 여기 1520 내리막길 문제는, 제가 무려 2년 전에 틀려놓고 그뒤로 방치했던 문제입니다. 무시무시한 런타임에러... 그래서 이제와서 다시 재도전해보려고 켜봤습니다. 문제 자체는 말이 쉽습니다. 숫자들이 주어지고, 대충 그걸 높이라고 치면 쭉 내리막길이 되도록 잘 내려가는 루트가 몇개나 있는지, 찾으면 되는 문제입니다. 너무 대놓고 '나 DP예요 DP!'라고 광고하는 거 아닌가 싶을 정도의 문제입니다. 대충 첫칸부터 시작해서 DPS로 탐색을 하는데, 이미 방문한 적 있는 곳이면 기록을 미리 해두고 그곳으로 가는 내리막길이 있음+그길로 가면 끝까지 갈 수 있음이면 그 경우의 수만큼 더해주면 되는 간단한 코드를 생각할 수 있습니다. 구현 자체는 크게 어렵지 않았습니다. m,n=map(int,input..