리유나의 항해일지

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

ACM-ICPC에 이번에도 참가하게 되었습니다! 일단 예선 전까지 열심히 연습해서 전국 본선 진출을 목표로 해봐야 할 것 같네요! 다른 팀원 두분이 다 저보다 훨씬 실력자셔서, 팀에 누는 안 끼칠 정도로만 힘내보려고 합니다 ㅠ 팀명은 아직 안 정해졌지만 나중에 정해지면 올릴...수도 있습니다.

오랜만입니다. PS연습을 다시 시작해서 감을 살리려고, boj에서 알고리즘 분류 별로 나누어진 카테고리를 들어갔는데, 이 문제가 왜인지 눈에 밟혔다. 문제는 여기 초등부 정올 문제였다고 하는데, 언뜻 봐서는 잘 방법이 떠오르지 않았다. 대충 그리디하게 하면 될 것 같은데...하는 생각을 하고 있었다.(사실 문제 분류도 그리디였다.) 그런데 의외로 그게 이런저런 케이스들도 생각 많이 해줘야 하고, 못할 것 같지는 않아서 어려울 거라고 생각했는데, 어차피 10!은 해봐야 4백만도 안되고, 그냥 완전탐색으로 해봐도 괜찮을 것 같았다. 결국 구현의 문제였고, 파이썬에는 itertools 모듈이 있어서 구현을 아주 간편하게 할 수 있었다.(만약 그렇지 않았더라면 아마 백트래킹으로 모든 경우를 찾는 게 가장 어려운..

어제 이 문제를 해결하고 가만 생각해보니, 아무래도 더 빠른 방법이 있을 것 같다는 생각을 지울 수가 없었다. 거기에, 결국 ICPC는 C++로 짜야 할텐데, C++로 짜는 방법도 생각해봐야 하지 않겠나는 생각을 했다. 더 빠른 방법은 사실 생각해보면 꽤 빠르게 나왔다. 처음에 두개의 합으로 된 리스트를 만들 때, 원소들을 추가하는 방식이 아니라 미리 길이 40만짜리 리스트에다가 1씩 추가하는 식으로 구현하면 O(n^2)만에도 풀 수 있었을 것 같다.(게다가 이 방법이 C++로 구현하는 데에도 조금 더 도움이 될 것 같다!) 이 생각을 하고 코드를 조금 수정해보았다.(Python) w,n=map(int,input().split()) L=list(map(int,input().split())) L.sort(..

작년에 ACM-ICPC 대회에 출전했던 적이 있었다. 내가 참가했던 팀은 5개 해결로 전체 80등 언저리로 본선 진출에는 실패했었는데, 올해에 다시 이 대회에 나가려고 생각을 하고 있다. 그 과정에서 작년에 제일 고민을 많이 해봤었던(그렇지만 결국 풀지는 못했던)Parcel 문제를 다시 떠올리게 되었고, 1년만에 문제에게 복수를 하러 가보려고 한다. 문제는 여기서 볼 수 있다. 쉽게 말해서 뒤에 주어진 정수들 중에서 4개 골라서 앞에서 주어진 정수를 합으로 되게 만들 수 있냐는 문제이다. 이런 문제에서 흔히 생각할 수 있는 방법은 다음과 같다. 1. 완전 탐색. 주어진 거 4개씩 고르는 경우를 다 찾아보면 된다. 구현은 재귀적으로 대충 하면 될 거 같다. 그러나 n이 5000개까지 가능하다. 4개씩 다 ..