2023 하계모각코 6회차 개인 목표 및 결과

일시

2023-08-12 13:00~ 16:00

목표

6회차에서는  동적프로그래밍 알고리즘 문제를 풀어볼 생각이다.

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

1028번: 다이아몬드 광산

결과

import sys
r,c=map(int,input().split())
mountain=[]
for _ in range(r):
    mountain.append(list(map(int,sys.stdin.readline().rstrip())))

dp_dia=[[[0]*2 for _ in range(c)] for _ in range(r)]
max_lcnt=0
max_rcnt=0

for i in range(r): # 모든 좌표 돌기
    for j in range(c):
        if mountain[i][j]==1:
            a=i; b=j; lcnt=1
            while a<r and b>=0 and b<c and mountain[a][b]!=0 and dp_dia[a][b][0]==0:
                a+=1; b-=1; lcnt+=1
            a-=1; b+=1; lcnt-=1

            a=i; b=j; rcnt=1
            while a<r and b>=0 and b<c and mountain[a][b]!=0 and dp_dia[a][b][1]==0:
                a+=1; b+=1; rcnt+=1
            a-=1; b-=1; rcnt-=1

            a=i; b=j
            while lcnt!=0:
                dp_dia[a][b][0]=lcnt
                a+=1; b-=1; lcnt-=1
            
            a=i; b=j
            while rcnt!=0:
                dp_dia[a][b][1]=rcnt
                a+=1; b+=1; rcnt-=1
result=0
for i in range(r):
    for j in range(c):
        lpt=dp_dia[i][j][0]; rpt=dp_dia[i][j][1]
        smallpt=min(lpt,rpt)-1
        if smallpt!=-1:
            if dp_dia[i+smallpt][j-smallpt][1]>=smallpt and dp_dia[i+smallpt][j+smallpt][0]>=smallpt:
                if result<smallpt+1:
                    result=smallpt+1
print(result)

단순 재귀 문제였지만 난이도가 있는 문제여서 푸는데 시간이 좀 오래걸린것 같다 아직 많이 부족함을 느꼈다