๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โŒจ๏ธ Language/swift

[์ฝ”๋“œํŠธ๋ฆฌ ์ฑŒ๋ฆฐ์ง€] 4์ฃผ์ฐจ - ์™„์ „ ํƒ์ƒ‰

by hyebin (Helia) 2023. 10. 4.
๋ฐ˜์‘ํ˜•

์ง€๋‚œ๋ฒˆ๊ณผ ๋™์ผํ•˜๊ฒŒ 746๐Ÿฅฒ

 

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

 

์ฝ”๋“œํŠธ๋ฆฌ | ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์ค€๋น„๋ฅผ ์œ„ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •์„

๊ตญ๊ฐ€๋Œ€ํ‘œ๊ฐ€ ๋งŒ๋“  ์ฝ”๋”ฉ ๊ณต๋ถ€์˜ ๊ฐ€์ด๋“œ๋ถ ์ฝ”๋”ฉ ์™•์ดˆ๋ณด๋ถ€ํ„ฐ ๊ฟˆ์˜ ์ง์žฅ ์ฝ”ํ…Œ ํ•ฉ๊ฒฉ๊นŒ์ง€, ๊ตญ๊ฐ€๋Œ€ํ‘œ๊ฐ€ ์—„์„ ํ•œ ์ปค๋ฆฌํ˜๋Ÿผ์œผ๋กœ ์ค€๋น„ํ•ด๋ณด์„ธ์š”.

www.codetree.ai

 

์ตœ๊ณ ์˜ 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)
๋ฐ˜์‘ํ˜•