리유나의 항해일지

870솔브 했습니다. 여전히 꿀문제 위주로 푼 것도 사실이긴 한데, 그래도 너무 그러는 것 같아서 1페이지에 있는 비교적 번호 빠른 문제들에 도전해봤습니다. 1014 컨닝: 사람을 그래프 정점으로, 컨닝할 수 있는/당할 수 있는 사람의 쌍을 그래프 간선으로 잇게 된다면 그래프에서 최대 얼마만큼의 independent set을 만들 수 있느냐는 문제가 됩니다. 처음에는 그래서 네트워크 플로우를 생각했는데 자기 양 옆 줄의 사람들만 컨닝할 수 있으니까, 결국 홀수번째 줄/짝수번째 줄로 각각 이분 그래프를 만들 수 있게 됩니다. 그래서 이건 Kőnig의 정리에 따라서 이분매칭 문제가 될 수 있고, 실제로 이분 그래프로 잘 만들어 주면 됩니다. 1017 소수 쌍: 자연수가 중복되지 않으니까, 1+1=2는 불가능..

850 솔브와 350등을 동시에 달성했습니다! 상당수의 문제는 solved 기준으로 브론즈4 돌면서 풀어서 사실 허수긴 한데, 그래도 세그먼트 트리나 레이지 프로퍼게이션, 2-SAT이랑 SCC등은 연습해서 의미가 있었다고 생각합니다. 앞으로 이정도 밸런스로 150개만 더 풀면 되겠네요 하루에 6문제만 풀면 된다(?)

오랜만입니다. 현재 810문제인데, 2019년 내로 1000솔브 하는 걸 목표로 해서 달려보기로 했습니다. 실패 시 무언가를 걸면 조금 더 좋을 거 같은데...이건 추천받아요! 아무튼간에 열심히 해볼게요!

최근에 solved.ac 생긴 걸 알고 이거 랭크가 겨우 골드 1이길래 슬퍼서(??)열심히 플래티넘 문제들 풀었더니 어느새 800솔브 달성했네요! 예전에(2년쯤 전)는 열심히 할 때 600솔 정도로 200등 언저리 갔었는데 유저가 많이 늘었는지 이렇게 해도 겨우 400등 안이네요 ㅠ 다시 잡는다면 좀 열심히 랭킹도 올리는 한편, 이번에 풀었던 여러 플래티넘 문제들에서 공부했던 세그먼트 트리 등등도 조만간 포스팅해보겠습니다!

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