개발하는 개구리

🐸 문제 정보 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 35.48m (failed) 📝 풀이 DP는 어렵다... 점화식이 안떠올라서 결국 검색으로 아이디어를 얻었다. 3차원 DP 리스트 선언 [row][col][직전 방향] 현재 방향과 다른 방향의 직전 요소들 중, 최솟값을 현재 요소와 더해줌 이 때, 각 행의 0번째 열과 마지막 열의 경우, 직전 방향에 유의해야함 0번째 열은 직전 ↘ 방향이 없다 마지막 열은 직전 ↙ 방향이 없다..

🐸 문제 정보 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 failed 📝 풀이 이번 문제는 점화식을 끝내 찾지 못하고 검색의 힘을 빌려 풀었다. DP는 DP인걸 알아도 점화식이 안떠오르면 손도 델 수 없는게 너무 슬프다... 풀이는 다른 블로그를 참고했다. 간단히 요약하자면 아래와 같다. 기본적으로 1로만 구성된 경우는 각 숫자마다 1개씩 존재함 숫자 2부터는, (본인 - 2)에서 숫자 1로만 구성된 경우가 곧..

🐸 문제 정보 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 failed 📝 풀이 오랜만에 failed... 문제를 보고 DP라는 것은 알았으나, 도저히 점화식과 아이디어가 떠오르지 않았다. 그리고 결국 검색해서 풀이를 살펴보니 LIS(가장 긴 증가하는 부분수열) 문제라는 것을 깨달았다. 유사한 문제는 이전에도 풀어본 적 있는데, 이 문제가 도대체 왜 LIS 문제지? 라고 생각했으나 이 문제의 입력에서 도출되는 가장 긴 증가하는 부분 수열은 곧 제대로 된 위치에 있는 아이들과 같기..

🐸 문제 정보 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 60+m 📝 풀이 이틀동안 풀지 못했다... 처음에 시도했던 방법은 3차원 DP였는데, 해당 분에 뛴 경우와 쉰 경우를 분리해서 마지막에 지침지수가 0인 경우 최대값을 구했다. 하지만 이렇게 풀면 어떻게해도 메모리 초과가 난다... 정말 많이 틀렸다.. 올바른 풀이 방법은 아래와 같다. DP로 풀되, 2차원이면 충분하다. 우선 지침지수가 0인 경우, 즉 dp[i][0]에는 직전에 쉬고 현재 분에도 쉰 거리를 대입한다. dp[..

🐸 문제 정보 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 43.56m 📝 풀이 처음에 당연히 BFS라고 생각하고 푸는 바람에 어마어마하게 시간이 소요됐다. 이후에 DP + 누적합인 것을 알았음에도 풀이 방법이 바로 떠오르지 않았다. 사실 DP 문제들 중에서는 점화식을 찾기 쉬운 편의 문제였음에도 이렇게 시간이 오래 걸린다는 것은... DP에 대한 연습이 부족하다는 것은 당연하고, DP는 연습해도 실전에서 못풀 가능성이 높다는게 무슨 소리인지 느낄 수 있었다. 누적합으로 (0,0..