[백준] 11660번:구간 합 구하기5(Java 자바)

[백준] 11660번:구간 합 구하기5(Java 자바)

728x90

문제

https://www.acmicpc.net/problem/11660

풀이 및 소스코드

이 문제는 N이 1024이고, 부분합을 100,000번 구해야 함

그때그때 부분합을 구하게 되면 n^2(1024*1024)*m(100,000) => 시간초과

따라서 dp로 풀어야 한다.

https://subbak2.tistory.com/65

이 분께서 설명을 아주 잘해주셨다 !!!

이해가 안되면 이거 보면 될 듯!!

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new StringBuilder(); st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[][] map = new int[n+1][n+1]; for(int i=1;i<=n;i++) { st = new StringTokenizer(br.readLine()); for(int j=1;j<=n;j++) { map[i][j] = Integer.parseInt(st.nextToken()); } } // 구간 합 dp에 저장 int[][] dp = new int[n+1][n+1]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j]; } } int x1, y1, x2, y2; for(int mm=0;mm

"); } System.out.println(sb); } }

반응형

from http://jainn.tistory.com/341 by ccl(A) rewrite - 2021-12-06 00:27:57