[Algorithm] Swift 백준 2167번

 

 

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

 

 

문제접근 

 

엄청 쉬운 문제인 줄 알고 가볍게 접근했지만 이해하기 매우 어려웠음.

 

그리고 주어진 

 

(i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하기가 까다로웠음!!

 

그래서 우선 2차원 배열의 합에 대해서 알아볼 필요가 있었음! 

 

 

정답풀이 

 

2차원 배열의 합에 대해서 모른다면 🔽

 

https://h2kangrok.tistory.com/53

[Algorithm] Swift 1차원, 2차원 배열의 합

 

이걸 우선 보고 오면 됨!!!!  

 

바로 정답 코드로 보겠음!!!

 

import Foundation

//첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다
let NM = readLine()!.split(separator: " ").map { Int(String($0))!}
let (N, M) = (NM[0], NM[1])

var arr:[[Int]] = []

// 다음 N개의 줄에는 M개의 정수로 배열이 주어진다
for _ in 0..<N {
    arr.append(readLine()!.split(separator: " ").map { Int(String($0))!})
}

//dp 0으로 배열을 만들어줌
var dp = Array(repeating: Array(repeating: 0, count: M + 1), count: N + 1)

// dp[1][1]부터 시작
for i in 1...N {
    for j in 1...M {
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i-1][j-1]
    }
}

// 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다.
let K = Int(readLine()!)!

// 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).
for _ in 0..<K {
    let ijxy = readLine()!.split(separator: " ").map{ Int(String($0))!}
    let (i, j, x, y) = (ijxy[0], ijxy[1], ijxy[2], ijxy[3])
    
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])
}

 

var dp = Array(repeating: Array(repeating: 0, count: M + 1), count: N + 1)

 

주어진 2차원 배열보다 사이즈가 1이 더 큰 0으로 가득 찬 dp 배열을 만들어 줌!!!

 

for i in 1...N {
    for j in 1...M {
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i-1][j-1]
    }
}

 

dp배열에 2차원 배열의 합을 넣어줌!! 

 

for _ in 0..<K {
    let ijxy = readLine()!.split(separator: " ").map{ Int(String($0))!}
    let (i, j, x, y) = (ijxy[0], ijxy[1], ijxy[2], ijxy[3])
    
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])
}

 

마지막으로 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구해주었음!!!

 

2차원 배열의 합을 모른다면 이 글로는 이해가 어려울 거 같음!! 

위 글을 읽고 왔으면 쉽게 이해가 될 거임!!  🔼