리유나의 항해일지

오랜만입니다. 리유나입니다. 최근 꾸준히 앳코더나 코포는 참여했지만 본진인 BOJ를 그렇게 열심히 하진 않았는데, 간만에 삘을 받아버린 바람에 이참에 8481이나 풀어야겠다! 하고 몇년을 묵힌 8481에 도전을 했습니다! 아마 16일 걸렸네요... 1. 그래서 이게 무슨 문젠데? 한국 PS판에서는 "8481"이라고 하면 그 자체만으로 이미 너무나도 유명한 숫자입니다. 저 문제는 "ONTAK 2010"이라는, 당시 폴란드 IOI 국가대표를 선발하는 시험에 출제된 문제고, 내용은 너무나도 간단합니다. 주어지는 숫자 0에서 10까지에 대해, 정해진 아웃풋 파일과 똑같은 것을 출력하면 됩니다. 사실 그걸로 끝이면 아무리 생각해도 국대 선발 문제도, 다이아 3 문제도, 유명 구데기 문제도 아닐텐데, 도대체 왜 그..

안녕하세요. 리유나입니다. 생각해보니 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..

https://www.acmicpc.net/problem/27533 27533번: 따로 걸어가기 첫째 줄에 정수 $N$과 $M$이 공백을 사이에 두고 주어진다. ($2 \le N, M \le 200\,000$) www.acmicpc.net 오래간만입니다. 리유나입니다. 어쩌다보니 한번 손을 놓게 된 뒤로 또 포스팅을 한참 못하게 되더라고요... 시험도 끝난 김에 뭐라도 다시 글을 올리려고 최근에 풀었던 조합론 문제를 하나 소개하려고 합니다! SUAPC 2023 Winter L번으로 나온 문제라고 하네요. 문제의 설명은 꽤나 귀엽고 재미있는데, 대강 요약하면 N*M 격자 위에서 최단경로로 이동하는 경우의 수를 구하는 문제입니다! 다만 여기서 조건이 추가로 붙는데, 토순이와 토준이가 크게 싸운 탓에, 출발점..

문제 링크는 이쪽입니다. 0. 이 문제는 도대체 뭔가? 제가 BOJ에서 풀었던, 아니 PS를 하면서 풀었던 모든 문제를 통틀어서 가장 시행착오를 많이 겪었던 문제가 아마 바로 이 문제가 아닐까 싶습니다. 생각보다 유명한 문제여서 solved.ac 기준 루비 4임에도 불구하고 제법 많은 사람들이 풀었지만, 그럼에도 결코 쉬운 문제는 아닙니다. 개인적으로 적어도 난이도 값은 무조건 하는 문제라고 생각합니다. 문제의 내용 자체는 사실 아주 간단한데, 어떤 자연수 n에 대해서 n을 제곱수들의 합으로 나타내라는 것입니다. 사용된 제곱수의 개수는 최소여야 하고요. 가령, n이 25라면 3^2+4^2로도 나타낼 수 있겠지만 5^2 하나로 나타내는 것이 더욱 적합하겠죠. 그런데 n의 범위가 10^18까지의 자연수네요...