Jenikeju

n번째 앱까지 비활성화했을때의 최소비용을 구한다면, 메모리를 1부터 최대 1000만까지 순회해야하므로 시간초과

n번째 앱까지 비활성화했을때의 할당되는 메모리 를 구한다면, N이 최대 100이고, 비용도 100이므로 10000 만큼 순회한다.

예시문제에서 첫번째 앱을 비활성화 한다면 다음과 같이 나타낼 수 있다.

첫번째 앱의 메모리는 30, 비용은 3이다.

이는 비용 3미만일 때, 비활성화할 수 없으므로 0을 넣고, 3부터는 비활성화를 할 수 있다.

두번째 앱의 메모리는 10, 비용은 0이다.

이는 비용이 0일때, 비활성화가 가능하므로 메모리를 할당받을 수 있다.

이때, 비용이 3이 주어졌을 때 첫번째 앱과 두번째 앱 모두 비활성화가 가능하므로 이전 행에 있던 값을 불러와 더해준다.

세번째 앱의 메모리는 20, 비용은 3이다.

비용이 0일때 두번째 앱을 비활성화 할 수 있으므로 이전 행에 있는 값을 불러온다.

비용이 3일때, 경우의수는 두가지다.

1. 첫번째(3), 두번째(0)을 비활성화 하는경우

2. 두번째(0), 세번째(3)을 비활성화 하는경우

1번 경우의수는 이전행에 저장되있는 값이다(40)

2번 경우의수는 이전행의 두번째비용를 뺀 위치에 있는 값과 세번째 앱의 메모리를 더한 값이 된다.(10+20)

이를 식으로 나타내면

1번: dp[i-1][j]

2번: dp[i-1][j-a] + m ( a: 비용, m: 할당되는메모리)

점화식으로 나타내면 dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + m) 이 된다.

비용이 6이 주어졌을 때,

dp[3][6] = max( dp[2][6] , dp[2][3] + 20(세번째앱의 메모리)) = 60이 되는것이다.

이를 코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]
var arr = [[0]]
let a1 = readLine()!.split(separator: " ").map{Int(String($0))!}
let a2 = readLine()!.split(separator: " ").map{Int(String($0))!}
var sum = a2.reduce(0, +)
var answer = Int.max
for i in 0..<N {
    arr.append([a1[i],a2[i]])
}
// dp[i][j]: i번째 앱, j의 비용을 들였을때, 할당되는 메모리
var dp = Array(repeating: Array(repeating: 0, count: sum + 1), count: N+1)

// 배낭문제
// dp[i][j]: max(dp[i-1][j], dp[i-1][j-a] + m) (a:비용, m:메모리)
for i in 1...N {
    for j in 0...sum {
        dp[i][j] = dp[i-1][j]
        if j - arr[i][1] >= 0 {
            dp[i][j] = max(dp[i][j], dp[i-1][j-arr[i][1]] + arr[i][0])
        }
        // 메모리 할당이 충분히 됬다면, 비용을 저장하고 최솟값 갱신
        if dp[i][j] >= M {
            answer = min(answer, j)
        }
    }
}
print(answer)

개인 프로젝트 개발하는 과정에서 데이터베이스를 바꾸고자 했다.

맨 처음엔 UserDefaults를 사용했다가, SQLite3로 변경했었다.

SQLite3로 변경한 이유는 범용성이 뛰어나기 때문에 알아두기 위해 사용했다.

내부DB 특성상 앱이 삭제되면 데이터도 같이 삭제되기 때문에 안정성이 떨어지긴하다.

그래서 외부DB로 바꾸고자 한다.

RandomStudy의 데이터 모델 변천사

이 프로젝트의 데이터모델은 총 세가지였다.

이에 따라 데이터 모델도 세개로 구현했지만, 찝찝한 마음이 있었다.

데이터 흐름이나 모델의 공통적인 변수들만 봐도 굳이 세개로 구현해야할까? 느꼈다.

UserDefaults로 구현했을 때 세개의 데이터모델을 사용했고,

SQLite로 변경하면서 데이터의 모델이 다르면 번거롭게 호출수가 많아질 듯 하여 데이터 모델을 통합시켰다.

SQLite3로 변경할 때 데이터모델도 통합시켰다.

할일을 저장하고, 불러오고 완료하는 데이터 흐름은 동일하다.

하지만 할일 데이터모델에서 done, date 변수는 필요가 없었고, 오늘의 할 일에선 date가 필요하지않았다.

그래서 임의의 값을 넣어두고, 데이터가 넘어갈때 추가하는 형식을 이용했다.

이게 맞는지 의심이 되는데, 외부DB로 변경할 때 문제점이 드러났다.

데이터베이스에는 원칙이 있다.

• 무결성
• 안정성
• 확장성

Firebase로 마이그레이션 하고나니 데이터베이스의 무결성 원칙을 위배하는 것이다.

할 일을 저장한 study

오늘의 할일을 저장한 todo를 보면 아예 같은 값이 저장되있는것을 볼 수 있다.

체크를 한다면 done이 1로 변경되어 다른값으로 되지만, 다른 관점으로 보자.

1. 서버로부터 데이터를 호출할 때

서로 다른 테이블이지만 값이 같다. 할 일과 오늘의 할일에 저장된 데이터를 부르기위해 두번의 호출을 해야한다.

값이 같은 데이터를 두번에 걸쳐서 호출한다는 것은 효율적인 방법일까?

이는 데이터가 많으면 많아질수록 더욱 더 효율성이 떨어진다.

2. 데이터 모델을 통합하지 않는다면?

데이터 모델을 통합하지 않는다면 데이터베이스도 서로 다른 데이터모델을 저장할 공간이 필요하고, 서버도 많은 모델을 전송해야 하기에

이는 효율적이지 않다고 생각한다.

위 두가지를 고려하여 데이터 구조를 설계 하고자 한다.

JSON파일이 들어왔을때, 데이터를 사용하려면 디코딩과정이 필요하다.

JSON의 데이터중 원하는 데이터는 데이터모델로 구현하지만,

해당 데이터가 존재하지 않는다면, 옵셔널로 지정하지 않으면 오류가 발생한다.

위의 데이터 모델을 무결성을 위배하지 않고, 한번의 호출로 데이터를 분리하기 위해 데이터모델을 다음과 같이 구현한다.

struct DataModel{
    let name: String
    let done: Bool?
    let date: Date?
}

이렇게 데이터 모델을 구현하고, 필터링은 값이 존재하는지 판단후 분리하기로 한다.

이렇게되면 데이터는 한번만 호출하고, 필터링을 거쳐서 세가지로 분리된다.

• 데이터 한번 호출
• 서버가 필터링
• 앱은 데이터받기

앱이 데이터 받고 필터링한다면 사용자가 데이터 호출을 했을 때, 보여지는 시간까지 지연될 수 있어서 보통 서버가 해주지만,

지금은 없는 관계로 앱이 데이터를 받고 필터링을 해보자.

이전에 데이터를 데이터모델 수만큼 호출하여 불러왔다면,

데이터를 한번 불러오고, VC에 맞춰서 분리한 모습이다.

데이터를 받아오는 시간이 길어진다면 사용자가 확인하는 시간이 그만큼 지연되므로 데이터늘 받아오는 횟수는 최소로 줄이고자 해야겠다.

내가 푼 풀이

접근방법: DP

암호를 해석하는 경우의수를 먼저 찾아보았다.

1. 주어진 암호가 1~26사이면 해석이 가능하다.

2. 암호가 10~26이면, [1, 1- ], [2, 2- ]로 경우의수가 더 늘어난다.

3. 암호에 0이 주어질 수도 있다.

0의 경우의수

1. 00: 앞 0은 10,20으로 사용되었어도, 0이 연속으로 오는경우 해석이 불가능하다.

2. 10, 20: 해석이 가능하다. 하지만 경우의수는 늘지않는다.

3. 30, 40, ... , 90: 해석이 불가능하다.

위 경우의 수를 토대로 암호의 첫번째 문구부터 마지막까지 탐색한다.

탐색할 때,

암호가 0이라면 --> 0의 경우의수를 탐색

암호가 0이 아니라면 --> 무조건 해석이 가능하고, 해석이 되더라도 이전 해석문 + [현재암호] 이므로 경우의수가 늘어나지 않는다.

현재 암호와 이전암호를 합쳐서 비교했을 때, 10이상 26이하라면

-> 2번 경우의수 처럼 경우의수가 더 늘어난다.

ex) 11 이 주어졌다면, 1을 해석했을땐 A 1가지지만, 11을 해석하면 AA와 K가 된다. (2가지)

네번째 암호 1이 주어졌을때, 이전암호와 합치면 11이된다.

이때 네번째 암호까지의 해석 경우의수는 BEA + [A], BE + [K] , YA + [A], Y +[K] 로 4가지가 된다.

dp[4] = (dp[4] +dp[3]) + (dp[4] + dp[2]) 가 된다.

세번째 암호가 주어졌을때, 이전암호와 합치면 51이되고, 이는 해석이 가능한 암호가 아니다.

세번째 암호까지의 해석 경우의 수는 이전 두번째 암호까지의 경우의수와 동일하다.

dp[3] = dp[3] + dp[2]

따라서 점화식을 다음과 나타낼 수 있다.

dp[n] = dp[n] + dp[n-1] (n > 0)

dp[n] = dp[n] + dp[n-2] (10 <= n <= 26)

코드로 구현하면 다음과 같다.

import Foundation

// 입력 받기
var str = Array(readLine()!).map{String($0)}
let n = str.count
str.insert("0", at: 0)
var alphabet = ["."]
var dp = Array(repeating: 0, count: str.count+1)
var chan = true
for i in 65...90 {
    alphabet.append(String(UnicodeScalar(UInt32(i))!))
}
dp[0] = 1

// dp[n]: n자리 암호코드를 변환할 수 있는 경우의 수
// 단, 0에 예외처리를 해야함. 코드는 1~26 A~Z까지 변환 가능하므로, 0 또는 26보다 큰수는 변환이 불가.(마찬가지로 00도 불가.)
for i in 1..<str.count {
    if i == 1 {
        // 첫번째 수가 0이면 애초에 변환 불가
        if Int(str[i])! == 0 {
            dp[n] = 0
            break
        } else {
            dp[i] = 1
        }
        continue
    }
    // 숫자가 0이라면, 세가지 경우의수가 존재
    // 앞자리가 1,2인 10 20 , 앞자리가 0인 00, 앞자리가 2보다 큰수 30, 40, 50 ...
    // 앞자리가 0이거나 앞자리가 2보다 큰수면 변환자체가 불가능
    // 앞자리가 1,2인경우는 경우의수가 늘어나지않음. 1 -> A , 10 -> J 1가지임
    if str[i] == "0" {
        if str[i-1] == "0" || Int(str[i-1])! > 2 {
            dp[n] = 0
            break
        }
    } else {
        dp[i] = (dp[i] + dp[i-1]) % 1000000
    }
    // 만약 앞자리수를 포함한 숫자가 10~26 이라면 경우의수가 늘어남. 1 -> A , 11 -> AA, L 1가지에서 두가지로 늘어난다.
    if Int(str[i-1] + str[i])! <= 26 && Int(str[i-1] + str[i])! >= 10 {
        dp[i] = (dp[i] + dp[i-2]) % 1000000
    }
}
print(dp[n])

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

내가 푼 풀이

접근방법: DP

각 좌석은 양 옆으로만 배치할 수 있다.

예시로 [1, 2, 3, 4] 좌석을 배치하는 경우의 수를 확인해보자.

[1]: [1] 1가지

[1, 2]: [1, 2], [2, 1] 2가지

[1, 2, 3]: [1, 2, 3], [2, 1, 3], [1, 3, 2] 3가지

[1, 2, 3, 4]: [1, 2, 3, 4], [2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3], [2, 1, 4, 3] 5가지

위 좌석 4개로 규칙을 알 수 있다.

3개의 좌석 배치수를 구할 때: (2개 좌석이 배치된경우) + (3의 위치를 바꾼 경우)

( [1,2] + [3]  , [2,1] + [3] ) + ( [1] + [3, 2] ) 으로 총 3가지

4개의 좌석 배치수를 구할 때: (3개의 좌석이 배치된 경우) + (4의 위치를 바꾸는 경우)

( [1,2,3] + [4] , [2,1,3] + [4] , [1,3,2] + [4]) + ( [1,2] + [4,3] , [2,1] + [4,3] )으로 총 5가지

이를 점화식으로 나타내면 다음과 같다. 

dp[n] = dp[n-1] + dp[n-2]

여기서 추가조건으로 vip석은 이동할 수 없다.

위 예제를 보면 vip를 제외한 좌석은 아래와 같다.

[1,2,3] , [5,6] , [8,9] 

각각 배치가능한 경우의 수를 구하면, 3 , 2 , 2 가 되고, 모두 곱하면 12가 나온다.

이렇게 vip좌석을 경계로 배치방법 수를 구하고 모두 곱해주면 결과가 나오게 된다.

코드에서는 중간 결과값을 저장하여 마지막 수와 곱해서 출력했다.

import Foundation

//입력받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var vip = [Int]()
for i in 0..<M {
    vip.append(Int(readLine()!)!)
}
// dp[n]: 중간 vip좌석 없이 n번째까지의 배치 경우의 수
var dp = Array(repeating: 1, count: N+1)
// vip좌석을 만나면 값을 저장할 변수
var mul = 1
var idx = 0
var vp = false

// 탐색
for i in 1...N {
    // vip좌석을 만나면 중간값 저장
    if idx < M && i == vip[idx] {
        idx += 1
        dp[i] = 1
        mul = dp[i-1] * mul
        vp = true
        continue
    }
    // 이전에 vip좌석이였다면 그 다음 배치경우의수는 좌석 1개이므로 1
    if vp {
        dp[i] = 1
        vp = false
        continue
    }
    // 첫번째 좌석은 경우의수가 1가지
    if i == 1 {
        dp[i] = 1
        continue
    }
    dp[i] = dp[i-1] + dp[i-2]
}
print(dp[N] * mul)
//print(mul)

내가 푼 풀이

접근방법 1: DFS(시간초과)

일반적인 DFS로 풀어봤다가 같은 경로를 재탐색하게되어 시간초과가 났다(31퍼에서 안오름..)

접근방법 2: DFS + DP

DFS로 탐색하면서, 탐색한 경로에 값을 저장해둔다. 다른 출발점에서 탐색할 때, 이미 탐색된 곳이라면 탐색하지 않는다.

예시로 출발점 1에서 탐색한 경로가 (1 - 2 - 3 - 5)라면, 각 도착점에 값을 저장해둔다.

그 다음 출발점 2에서 탐색한다면 (2 - 3 - 5)로 재탐색하게된다.

이는 이전에 1번에서 탐색했고, 2번에서 출발해도 최댓값은 1번에서 출발한 크기 4가 된다.

1번 출발점에서 조건에 맞춰 갈 수 있는 모든 지점을 도달했고,

그 지점마다 이동한 칸수가 저장되어 있으므로, 다시 재탐색을 할 필요가 없다.

DP[y][x]: (x,y)지점에서 이동할 수 있는 칸의 최댓값

코드로 구현하면 다음과 같다.

import Foundation

// 입력 받기
let n = Int(readLine()!)!
var arr = [[Int]]()
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// dp[y][x]: (x,y)에서 최대로 이동할 수 있는 수
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
var result = 0

// 상,하,좌,우 4방향
let dx = [0,1,0,-1]
let dy = [1,0,-1,0]

// DFS + DP
// DFS로 깊이 탐색하며, 최대로 이동한 값을 저장한다.
// DP에 저장하는이유: 이미 최대로 이동한 경로를 재탐색 하지 않기 위해서
// 예시) (1 - 2 - 3 - 4)로 이동한게 최대라면, 2번에서 이동경로는 (2 - 3 - 4)를 갖게된다.
// 2번에서 이동한 경로는 이미 탐색된 경로이므로 굳이 다시 탐색하지않아도된다. (가지치기)
func dfs(_ x: Int,_ y: Int) -> Int {
    // 이미 이동했던 경로라면 종료
    if dp[y][x] != 0 { return dp[y][x] }
    // 이동했던 경로로 표시
    dp[y][x] = 1
    // 네방향으로 조건에 맞춰서 이동
    for k in 0..<dx.count {
        let mx = x + dx[k]
        let my = y + dy[k]
        if (mx >= 0 && mx < n) && (my >= 0 && my < n) {
            if arr[my][mx] > arr[y][x] {
                dp[y][x] = max(dp[y][x], dfs(mx, my) + 1)
            }
        }
    }
    return dp[y][x]
}
// 모든 시작점에서 출발해보고, 최댓값을 구한다.
for i in 0..<n {
    for j in 0..<n {
        result = max(result, dfs(j, i))
    }
}
print(result)

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

내가 푼 풀이

접근방법: DP

이 문제는 이전에 풀었던 파일합치기 문제와 유사하다

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

 

연산에 순서에 따라 총 연산횟수가 달라지는 행렬곱셈으로, DP를 이용해 풀었다.

가장 좁은 구간부터 연산횟수를 구하고 저장하여 구간을 넓히며 값을 구해나갔다.

 

dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱셈연산의 최솟값 이고,

dp[i][i] = 0이다.( dp[1][1] == dp[2][2] == dp[i][i] = 0, 행렬한개로 곱셈을 하지않는다.)

예시를 통해 알아보자.

dp 2차원배열을 다음과 나타낼 수 있다.

각 행과 열은 행렬의 크기를 나타낸다.

최종적으로 dp[1][3]을 구하기 위해 작은 구간부터 칸을 채워나가보자.

구간의 길이가 2일때 : [1,2], [2,3]

위 2차원 배열에선 dp[1][2], dp[2][3]의 값을 구하는것이다.

구간의 길이가 2일땐, 순서상관없이 연산횟수가 같다.(순서는 바꾸면안된다. 행렬곱셈이 안됨)

dp[1][2] =  $5\times3\times2$ = $30$

dp[2][3] =  $3\times2\times6$ = $36$

구간의 길이가 3일때: [1,2] + 3, 1 + [2,3] 

위와 다르게 표현한 이유는 점화식으로 표현하기 위해서이다.

결국 구간 [1,2,3]의 값이 저장된 dp[1][3]을 구하는 것이지만,

[1,2] 와 [2,3]은 이미 이전에 구한뒤 저장해두었다.

dp[1][2] $\times$ [3]과 [1] $\times$ dp[2][3]의 결과중 최솟값을 넣으면 된다.

dp[1][2] $\times$ [3]: dp[1][2] + ($5 \times 2 \times 6$) = 90(1번행렬과 2번행렬을 곱하면 5x2 배열)

[1] $\times$ dp[2][3]: dp[2][3] + ($5 \times 3 \times 6$) = 126(2번행렬과 3번행렬을 곱하면 3x6 배열)

따라서 dp[1][3]은 더 작은값 90을 저장한다.

정리)

1. N개의 행렬이 주어지면 dp[1][N]의 값을 구한다.(dp[1][N]: 1번째행렬부터 N번째 행렬까지 연산의 최소횟수)

2. 가장작은 구간의 곱셈부터 구하고 최솟값을 저장한다.

3. 저장된 구간으로부터 더 넓은 구간의 연산횟수를 구한다.(최솟값을 비교하여 저장)

4. 최종적으로 dp[1][N]을 구한다.

예시: [1,2,3,4,5]

구간 2: [1,2], [2,3], [3,4], [4,5]

구간 3: [1,2,3], [2,3,4], [3,4,5]

구간 4: [1,2,3,4], [2,3,4,5]

구간 5: [1,2,3,4,5]

점화식은 다음과 나타낼 수 있다.

$\mathbf{dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + ((j행 \times k열 \times i+j열)(k: i와 i+j 사이의 점)} $

3중 for문을 이용하여 코드를 구현해보자.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: 0, count: 2), count: N+1)

// 주어진 행렬들의 행,열 저장
for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][0] = input[0]
    arr[i+1][1] = input[1]
}

// dp[i][j]: i번째부터 j번째까지 연산의 최소횟수
// 가장 좁은구간부터 구한 값을 이용해 넓은 구간의 최솟값을 구한다.
for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][0] * arr[k][1] * arr[i+j][1]))
        }
    }
}
print(dp[1][N])

배열의 크기를 무분별하게 크게 선언했다가 시간초과가 났다..

행렬들의 행,열은 곱셈을 하면 결과의 행,열이 변할 수 있어도, 값 자체가 변하진 않는다. (피연산 행렬들의 행 열을 가져옴)

(5x2와 2x3의 결과가 왼쪽행렬의 행, 오른쪽행렬의 열을 가져와 5x3이 되는것처럼)

이를 이용해 2차원배열에 저장해두었다.

아예 튜플로 저장하여 문제풀이를 시도했지만, 시간초과가 났다.

시간초과가 난 코드

import Foundation

let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: (x: 0, y: 0), count: N+1), count: N+1)

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][i+1] = (x: input[0], y: input[1])
}

for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][k].x * arr[j][k].y * arr[k+1][j+i].y))
            arr[j][j+i] = (x: arr[j][k].x, y: arr[k+1][j+i].y)
        }
    }
}

print(dp[1][N])

내가 푼 풀이

접근방법: 부분합

이전에 체스판 다시 색칠하기 1 문제는 브루탈포스로 모든 경우의수를 구해서 대입하고 구했다면,

이 문제는 체스판의 크기가 최대 2000 x 2000 이므로 브루탈포스로는  시간초과가 난다.

부분합을 이용해서 구해보자

주어진 수열에서 i번째까지의 합은 다음과 같다.

 $S_{i} = A(i) + A(i-1) + \cdots + A(1) $

이 성질을 이용해 부분합 i부터 j까지의 합은 다음과 같다.

$S_{ij} = A(j) + A(j-1) + A(j-2) +\cdots + A(i+1) + A(i) = S_{j} - S_{i-1}$

이것을 2차원 배열에 적용하는데, 체스판은 총 두가지 경우가 있다.

• 왼쪽상단이 검정색으로 시작하는 경우
• 왼쪽상단이 흰색으로 시작하는 경우

두개의 체스판을 이용하여 2차원배열 부분합을 구한다.

먼저 예시의 체스판과 두개의 정상 체스판을 보자.

Board: 주어진 보드판, Black: 왼쪽 상단이 검정으로 시작, White: 왼쪽 상단이 흰색으로 시작

주어진 보드판을 두개의 정상 체스판처럼 만들어보려고 한다.

보드에서 각 칸과 정상 체스판의 색이 같다면 색칠하지 않아도되고, 색이 다르면 색칠을 해줘야 한다.

i행 i열의 값은 1행1열부터 i행 i열까지 색칠한 수를 모두 합한 수가 되도록 구해준다.

이렇게 2차원배열로 부분합을 구해주면 위와 같다.

배열 S[i][j] : 1행1열부터 i행i열까지의 합

여기서 주어진 K x K 크기의 체스판을 만들 때 최소로 색칠하는 횟수를 구하려고 한다.

각 배열의 원소는 1행1열부터 색칠한 횟수를 저장했다.

부분합 성질을 이용하여 K크기의 체스판을 만들고, 색칠하는 최솟값을 갱신한다.

예시로 중간 2행2열부터 3행3열까지의 부분합을 구해보자.

이를 식으로 나타내면

S[3][3] - S[3][1] - S[1][3] + S[1][1]

이렇게 K x K 크기만큼의 부분합을 구해서 최솟값을 구하면 된다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2]

// 체스판의 맨 왼쪽상단이 검정색, 흰색인경우의 두가지 정상 체스판을 미리 만든다.
var black = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var white = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var first = false
var bl = true
var minSum = Int.max
for i in 1...N {
    if first {
        bl = true
    } else {
        bl = false
    }
    first = !first
    for j in 1...M {
        if bl {
            white[i][j] = 1
        } else {
            black[i][j] = 1
        }
        bl = !bl
    }
}

// 부분합 구하기
for i in 0..<N {
    let arr = Array(readLine()!)
    for j in 0..<arr.count {
        if (black[i+1][j+1] == 0 && arr[j] == "B") || (black[i+1][j+1] == 1 && arr[j] == "W") {
            black[i+1][j+1] = black[i+1][j] + 1 + black[i][j+1] - black[i][j]
        } else {
            black[i+1][j+1] = black[i+1][j] + black[i][j+1] - black[i][j]
        }
        if (white[i+1][j+1] == 0 && arr[j] == "B") || (white[i+1][j+1] == 1 && arr[j] == "W") {
            
            white[i+1][j+1] = white[i+1][j] + 1 + white[i][j+1] - white[i][j]
        } else {
            white[i+1][j+1] = white[i+1][j] + white[i][j+1] - white[i][j]
        }
    }
}

// 해당 부분합중 최솟값 구하기
for i in 1...N-K+1 {
    for j in 1...M-K+1 {
        let whiteSum = white[i+K-1][j+K-1] - white[i+K-1][j-1] - white[i-1][j+K-1] + white[i-1][j-1]
        let blackSum = black[i+K-1][j+K-1] - black[i+K-1][j-1] - black[i-1][j+K-1] + black[i-1][j-1]
        let m = min(whiteSum, blackSum)
        minSum = min(minSum, m)
    }
}
print(minSum)

인덱스의 0번째부터 6번째순으로 사람이 줄 서 있다. 이를 그래프로 나타내면 아래와 같다.

첫번째 위치한 사람의 키는 2이고, 두번째 위치한 사람의 키는 4이다.

위 첫번째 조건에따라 두 사람은 서로 볼 수 있는 쌍이 된다.

이제 세번째 위치한 사람을 보자.

첫번째 키는 2, 세번째 키는 1이된다. 서로 볼 수 있을까?

3번 조건에 따르면 서로 볼 수 없는 쌍이다.

세번째 이후의 모든 사람들도 1번사람과 볼 수 있는 쌍이 될 수 있을까?

답은 X다. 왜냐하면 첫번째사람보다 두번째사람이 더 크기때문에, 3번 조건에 의해 볼 수 없는 쌍이 된다.

그렇다면 1번은 2번에 의해서 항상 가려지기때문에 1번의 키정보는 필요가 없다.

순차적으로 키를 조사할때, 현재 사람의 키가 이전사람보다 크다면, 이전사람의 키는 더이상 필요가없게된다.

즉 우리는 스택에 이전사람의 키를 저장하고, 이전사람의 키보다 현재사람의 키가 더 크다면,

그 이후사람들은 어차피 못보게되므로, 스택에서 빼내어 볼 수 있는 쌍을 구한다.

-> 내림차순으로 구성된 스택에서 상단 원소보다 현재 원소가 더 크다면, 현재원소보다 작거나 같은 원소는 모두 pop ,

이때 볼 수 있는 쌍을 구한다.

5번째 사람의 서로 볼 수 있는 쌍을 구해보자.

첫번째 사람은 두번째사람에 의해 볼 수 없다.

두번째 사람은 서로 볼 수 있는 쌍이다.

세번째 사람은 네번째 사람에 의해 볼 수 없다.

네번째 사람은 키가 같고 인접해있으므로 볼 수 있다.

이때 스택에는 현재 사람보다 키가 큰 인원만 저장한다.

(저장되어 있는 원소중에 현재 키보다 작은 사람들은 pop하여 쌍의 개수를 세주었다.)

스택에서 값이 빠지는 과정

이때 키가 같다면 키가 같은 인원을 추가해주고 스택에 저장한다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = [Int]()
// 스택에 튜플형식으로 저장
// 같은 높이의 인원도 볼 수 있으므로
var stack = [(num: Int, height: Int)]()
var count = 0
for i in 0..<N {
    arr.append(Int(readLine()!)!)
}
print(arr)
for i in 0..<arr.count {
    var current = (num: 1, height: arr[i])
    // 현재 사람의 높이보다 작거나 같은 인원들은 모두 볼 수 있는사람들이다.
    // 해당 인원들은 모두 볼 수 있는 쌍이 되므로, 그만큼 count를 더해준다.
    // 키가 같은 인원도 볼 수 있으므로, 키가 같다면 키가 같은 인원수를 더해서 스택에 다시 넣어준다.
    while !stack.isEmpty && stack.last!.height <= current.height {
        if stack.last!.height == arr[i] {
            count += stack.last!.num
            current.num += stack.removeLast().num
        } else if stack.last!.height < arr[i] {
            count += stack.removeLast().num
        }
    }
    // 스택은 키가 내림차순으로 저장된다.
    // 스택에 값이 존재한다면, 이는 내림차순으로 정렬되었을때
    // 현재 사람과 바로 직전의 사람과의 중간은 사람이 존재하지않으므로 무조건 볼 수 있는 사이다.
    if !stack.isEmpty {
        count += 1
    }
    stack.append(current)
}
print(count)