[코드트리 챌린지] 4주차 - 완전 탐색

지난번과 동일하게 746🥲

 

https://www.codetree.ai/cote/14/problems/best-place-of-13-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

최고의 13위치 2

문제

N * N 크기의 격자 정보가 주어집니다. 이때 해당 위치에 동전이 있다면 1, 없다면 0이 주어집니다. N * N 격자를 벗어나지 않도록 1 * 3 크기의 격자 2개를 서로 겹치지 않게 적절하게 잘 잡아서 해당 범위 안에 들어있는 동전의 개수를 최대로 하는 프로그램을 작성해 보세요. 단, 1 * 3 크기의 격자는 세로로는 1, 가로로는 길이 3으로만 이루어지게 잡아야만 하며, 회전시킬 수 없음에 유의합니다.

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 N이 주어집니다.

두 번째 줄부터는 N개의 줄에 걸쳐 격자에 대한 정보가 주어집니다. 각 줄에는 각각의 행에 대한 정보가 주어지며, 이 정보는 0또는 1로 이루어진 N개의 숫자로 나타내어지며 공백을 사이에 두고 주어집니다.

• 3 ≤ N ≤ 20

출력 형식

N * N 격자를 벗어나지 않으면서, 겹치지 않는 1 * 3 크기 격자 2개 내에 들어올 수 있는 최대 동전의 수를 출력해주세요.

입출력 예제

예제 1

입력:

3
1 0 1
0 1 0
0 0 0

출력:

3

 

예제 2

입력:

5
0 0 0 1 1
1 0 1 1 1
0 1 0 1 0
0 1 0 1 0
0 0 0 1 1

출력:

5

제한

시간제한: 1000ms
메모리 제한: 80MB

---

풀이

가능한 모든 1*3 크기의 격자의 위치 2곳을 잡아보며, 그중 최대 동전의 개수를 구한다. 

첫 번째 격자와, 두 번째 격자 위치를 잡은 후, 두 격자가 겹치는 경우에는 동작을 수행하지 않는다.

두 격자가 겹치는 않는 경우에만 동전의 수를 세어 가장 많은 동전의 개수를 구한다.

코드

let n = Int(readLine()!)!
var arr = [[Int]]()
var max_cnt = 0

for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

for i in 0..<n {
    for j in 0..<n-2 {
        for k in 0..<n {
            for l in 0..<n-2 {
                if i == k && abs(j-l) <= 2 {continue}
                
                let cnt1 = arr[i][j] + arr[i][j + 1] + arr[i][j + 2]
                let cnt2 = arr[k][l] + arr[k][l + 1] + arr[k][l + 2]
                max_cnt = max(max_cnt, cnt1+cnt2)
            }
        }
    }
}
print(max_cnt)