potato's devlog

🟠 문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp 문제중 하나였다. 하지만 가장 중요한것은, 생각을 반대로해야한다는 것이었다. "처음부터 계단을 어떻게 올라가지?" 생각보다는, "최종 도착지기준으로 봤을때, 어디서 올라왓찌?"를 고려해봐야한다는 것이다. 연속으로 3칸의 계단을 밟을 수가 없기 때문에, 도착지 기준으로 올라올 수 있는 방법은 아래 그림처럼 딱 두가지 방법이다. 이렇게 dp 점화식을 유도해냈..

✅ 문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net ✅ 문제 풀이 아이디어 문제가 굉장히 난해하게 생겼기 때문에 ,,,, 처음엔 BFS 문제인지 감이 안잡혔다. 인터넷을 찾아보니, 이 문제의 핵심은 다음과 같았다. 가운데 구멍뚫린 부분은 신경쓰지 않아도 된다. 어차피 BFS 로 탐색을 (0,0)부터 시작하게되면, 구멍으로 접근이 불가능하다. 외부 공기자리부터 탐색을 시작하면 어차피 구멍 내부로 접근할 수 없기떄문!! 가장자리는 항상 외부공기로 둘러쌓여있..

✅ 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ✅ 문제 풀이 아이디어 기본적으로 연합국가인지 아닌지를 판단해야하기 때문에 BFS로 풀어야한다고 생각했다. 위의 출력예제를 보면, 점선이 생기는 위치가 다르다. 30과 40은 직접적인 연결은 아니지만, 어쨋든 연합국가이긴하다. 그렇기 때문에 초반에 어렵게만 생각되었던 "어디에 점선이생기는지 고려해야하는가"를 전혀 생각하지 않고 그냥 탐색하면서 연합국가에 같이 담아주면된..