![]()
문제https://www.acmicpc.net/problem/11660 여담저번에 풀었던 문제임에도 불구하고 까먹어서 결국 풀이를 참고했다. 그때도 완전히 익히지 않고 넘어갔다는 뜻이겠지..? 이런식으로 설렁설렁 넘어간게 대체 몇 개인지🤦🏻♀️ 이번에는 좀 익히자.. 풀이2차원 테이블을 사용해서 누적합을 구하면 되는 문제이다. 우선 배열의 값들을 입력받은 후, 아래의 점화식을 이용해 dp 테이블을 채워야 한다.dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j] 누적합을 이용해 dp 테이블을 채운 후, 이제 원하는 영역의 누적합을 구해야 한다. 이를 위해 다음 그림과 같이 각 구간의 누적합을 더하고 빼주면 된다. 코드import java.i..
![]()
문제https://www.acmicpc.net/problem/10844 여담저번에 풀려고 시도했다가 풀지 못해서 그냥 나뒀던 문제였다.. 그치만 계속 외면할 수는 없어서 풀이를 참고해서 풀었다.표를 그려서 풀었다면 규칙을 찾아낼 수 있었을텐데 계속 다른 방식으로 삽질해서 아쉬웠다😂 DP 오랜만에 푸니까 너무 어렵다..!! 풀이이 문제는 규칙만 찾아내면 쉽게 풀이할 수 있다. 참고한 블로그의 표를 보고 쉽게 이해했으므로, 나도 표를 이용해서 설명하려고 한다.해당 문제는 인접한 모든 자리의 차이가 1이다. 따라서 0에서 9까지의 숫자 뒤에 올 수 있는 숫자들의 특징은 다음과 같다.앞의 자리가 0 ⇒ 다음 자리는 무조건 1앞의 자리가 9 ⇒ 다음 자리는 무조건 8앞의 자리가 1 ⇒ 다음 자리는 0 또는 2앞..
