๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/14500)
<ํ ํธ๋ก๋ฏธ๋ ธ>
๋ฌธ์
ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1 ×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค.
- ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค.
- ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค.
- ์ ์ฌ๊ฐํ์ ๋ณ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ฆ, ๊ผญ์ง์ ๊ณผ ๊ผญ์ง์ ๋ง ๋ง๋ฟ์ ์์ผ๋ฉด ์ ๋๋ค.
์ ์ฌ๊ฐํ 4๊ฐ๋ฅผ ์ด์ด ๋ถ์ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํ ํธ๋ก๋ฏธ๋ ธ๋ผ๊ณ ํ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ 5๊ฐ์ง๊ฐ ์๋ค.
์๋ฆ์ด๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ข ์ด ์์ ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ๋์ผ๋ ค๊ณ ํ๋ค. ์ข ์ด๋ 1 ×1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์์ผ๋ฉฐ, ๊ฐ๊ฐ์ ์นธ์๋ ์ ์๊ฐ ํ๋ ์ฐ์ฌ ์๋ค.
ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ์ ์ ํ ๋์์ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ฌ ์๋ ์๋ค์ ํฉ์ ์ต๋๋ก ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
ํ ํธ๋ก๋ฏธ๋ ธ๋ ๋ฐ๋์ ํ ์ ์ฌ๊ฐํ์ด ์ ํํ ํ๋์ ์นธ์ ํฌํจํ๋๋ก ๋์์ผ ํ๋ฉฐ, ํ์ ์ด๋ ๋์นญ์ ์์ผ๋ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ข ์ด์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (4 ≤ N, M ≤ 500)
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ข ์ด์ ์ฐ์ฌ ์๋ ์๊ฐ ์ฃผ์ด์ง๋ค. i๋ฒ์งธ ์ค์ j๋ฒ์งธ ์๋ ์์์๋ถํฐ i๋ฒ์งธ ์นธ, ์ผ์ชฝ์์๋ถํฐ j๋ฒ์งธ ์นธ์ ์ฐ์ฌ ์๋ ์์ด๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ์๋ 1,000์ ๋์ง ์๋ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ธ ์๋ค์ ํฉ์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
๋ฌธ์ ํ์ด
- my solution (Python)
import sys
def main():
n,m=map(int, sys.stdin.readline().split()) # ์ธ๋ก, ๊ฐ๋ก
arr=[]
for i in range(n):
arr.append(list(map(int,sys.stdin.readline().split())))
result=0
Fig_1_x=[0,1,2,3]
Fig_1_y=[0,0,0,0]
for i in range(n):
for j in range(m):
flag_a=True;flag_b=True;temp_a=0;temp_b=0
for k in range(4):
x_1=i+Fig_1_x[k]
y_1=j+Fig_1_y[k]
if 0<=x_1<n and 0<=y_1<m:
temp_a+=arr[x_1][y_1]
else:
flag_a=False
x_2=i+Fig_1_y[k]
y_2=j+Fig_1_x[k]
if 0<=x_2<n and 0<=y_2<m:
temp_b+=arr[x_2][y_2]
else:
flag_b=False
if flag_a==True and result<temp_a:
result=temp_a
if flag_b==True and result<temp_b:
result=temp_b
Fig_2_x=[0,0,1,1]
Fig_2_y=[0,1,0,1]
for i in range(n):
for j in range(m):
temp=0; flag=True
for k in range(4):
x=i+Fig_2_x[k]
y=j+Fig_2_y[k]
if 0<=x<n and 0<=y<m:
temp+=arr[x][y]
else:
flag=False
break
if flag==True and result<temp:
result=temp
Fig_3_x=[[0,1,2,2],[0,1,2,2],[0,0,1,2],[0,0,1,2]]
Fig_3_y=[[0,0,0,1],[0,0,0,-1],[0,-1,-1,-1],[0,1,1,1]]
for i in range(n):
for j in range(m):
for k in range(4):
cnt_a = 0;cnt_b = 0;temp_a = 0;temp_b = 0
for v in range(4):
x_1=i+Fig_3_x[k][v]
y_1=j+Fig_3_y[k][v]
if 0<=x_1<n and 0<=y_1<m:
cnt_a+=1
temp_a+=arr[x_1][y_1]
x_2=i+Fig_3_y[k][v]
y_2=j+Fig_3_x[k][v]
if 0<=x_2<n and 0<=y_2<m:
cnt_b+=1
temp_b+=arr[x_2][y_2]
if cnt_a==4 and result<temp_a:
result=temp_a
if cnt_b==4 and result<temp_b:
result=temp_b
Fig_4_x=[[0,0,1,0],[0,0,-1,0],[0,0,-1,1],[0,0,-1,1]]
Fig_4_y=[[0,1,1,2],[0,1,1,2],[0,1,1,1],[0,-1,-1,-1]]
for i in range(n):
for j in range(m):
for k in range(4):
cnt_a = 0;temp_a = 0
for v in range(4):
x_1=i+Fig_4_x[k][v]
y_1=j+Fig_4_y[k][v]
if 0<=x_1<n and 0<=y_1<m:
cnt_a+=1
temp_a+=arr[x_1][y_1]
if cnt_a==4 and result<temp_a:
result=temp_a
Fig_5_x=[[0,1,1,2],[0,1,1,2]]
Fig_5_y=[[0,0,1,1],[0,0,-1,-1]]
for i in range(n):
for j in range(m):
for k in range(2):
cnt_a = 0;cnt_b = 0;temp_a = 0;temp_b = 0
for v in range(4):
x_1=i+Fig_5_x[k][v]
y_1=j+Fig_5_y[k][v]
if 0<=x_1<n and 0<=y_1<m:
cnt_a+=1
temp_a+=arr[x_1][y_1]
x_2=i+Fig_5_y[k][v]
y_2=j+Fig_5_x[k][v]
if 0<=x_2<n and 0<=y_2<m:
cnt_b+=1
temp_b+=arr[x_2][y_2]
if cnt_a==4 and result<temp_a:
result=temp_a
if cnt_b==4 and result<temp_b:
result=temp_b
print(result)
if __name__=='__main__':
main()
Fig_1_x, Fig_1_y
= ํ์ , ๋์นญ์ ์์ผ๋ ๋ ๊ฐ์ง ๊ฒฝ์ฐ ๋ฐ์ ์๋ค. ํ์ง๋ง 2์์ฉ x์ y ๊ฐ์ด ๊ฐ๊ฐ y์ x ๊ฐ๊ณผ ๊ฐ์ผ๋ฏ๋ก 1๊ฐ์ ์ขํ๋ก ๊ตฌํ ์ ์๋ค.
Fig_2_x, Fig_2_y
= ํ์ , ๋์นญ์ ์์ผ๋ ํ ๊ฐ์ง ๊ฒฝ์ฐ ๋ฐ์ ์๋ค.
Fig_3_x, Fig_3_y
= ํ์ , ๋์นญ์ ์ํค๋ฉด 8๊ฐ์ง์ ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ๋ค. ํ์ง๋ง 2์์ฉ x์ y๊ฐ์ด ๊ฐ๊ฐ y์ x๊ฐ๊ณผ ๊ฐ์ผ๋ฏ๋ก 4๊ฐ์ ์ขํ๋ก ๊ตฌํ ์ ์๋ค.
Fig_4_x, Fig_4_y
= ํ์ , ๋์นญ์ ์ํค๋ฉด 4๊ฐ์ง์ ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ๋ค.
Fig_5_x, Fig_5_y
= ํ์ , ๋์นญ์ํค๋ฉด 4๊ฐ์ง์ ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ๋ค. ํ์ง๋ง 2์์ฉ x์ y๊ฐ์ด ๊ฐ๊ฐ y์ x ๊ฐ๊ณผ ๊ฐ์ผ๋ฏ๋ก 2๊ฐ์ ์ขํ๋ก ๊ตฌํ ์ ์๋ค.
- ์ธ๋ก n, ๊ฐ๋ก m ์ ๋ ฅ
- arr : ์ข ์ด์ ์ฐ์ฌ ์๋ ์ ์ ๋ ฅ
- result = ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ธ ์๋ค์ ํฉ์ ์ต๋๊ฐ
- Fig_n_x, Fig_n_y : ๊ฐ ํ ํธ๋ก๋ฏธ๋ ธ์ ์ขํ
- Fig_n_x, Fig_n_y๋ฅผ ํตํด ๊ฐ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ฌ ์๋ ์๋ค์ ํฉ์ ๊ตฌํ์ฌ ํฉ์ด ์ต๋์ธ ๊ฐ์ ๊ตฌํด์ค๋ค.
- result ์ถ๋ ฅ
โ ์ ํ๋ ธ๋๊ฐ?
์ด๊ธฐํํด์ฃผ๋ ์์น๋ฅผ ์๋ชป ์ค์ ํ์ฌ ํ๋ ธ๋ค. ๊ฐ๋จ..? ํ๊ฒ ํด๊ฒฐ~
์๊ฐ๐ค
๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ ์ฉ์์ผ ๋ต์ ๊ตฌํด๋ ์๊ฐ ์ด๊ณผ๋ฅผ ํผํด ๊ฐ ์ ์์๊น ํ๋๋ฐ ํต๊ณผํ๋ค ใ ใ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 2564_๊ฒฝ๋น์ (0) | 2022.06.10 |
---|---|
[Baekjoon] 3184_์ (0) | 2022.06.02 |
[Baekjoon] 21608_์์ด ์ด๋ฑํ๊ต (0) | 2022.05.27 |
[Baekjoon] 16236_์๊ธฐ ์์ด (0) | 2022.05.26 |
[Baekjoon] 17086_์๊ธฐ ์์ด 2 (0) | 2022.05.20 |