7개의 댓글이 있습니다.
-
-
Signin -
음... 이건 최소 시간인지는 모르겠지만 그냥 떠오른 건데요,
아직 덮여지지 않은 칸 중 가장 (y,x)좌표가 빠른 칸을 골라서,
거기서부터 y축 or x축 방향으로
직사각형을 확장시켜나가면 어떨까요?예를 들면 저 예제에서는, 첫 스타트가 (0,1)에서 시작해서,
최대로 확장하면 가로로 3, 세로로 3인 사각형이 됩니다.
이제 덮여지지 않는 곳 중에 가장 빠른 번호는
마지막 (3, 2)이므로, 이건 그냥 사각형 하나로 덮어주면 될 것 같아요.여기 예제에서는 굳이 중첩되게 덮을 필요가 없지만,
중첩되는 경우가 생기더라도
값을 다르게 표현해서(ex. 덮인 칸들은 2로 해서, 1 이상이면 덮기 가능)
덮을 수 있는 상태를 표현하면 뭔가 되지 않을까... 싶습니다막 떠오른 생각이라, 틀린 점이 많을 수 있는데
태클 해 주시면 감사하겠습니다.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
rlagudwlscjs
시간복잡도를 최소화 하고 싶은데. 단순한 방법뿐이 떠오르지 않아서요
다양한 분들의 의견을 듣고자 질문올립니다.
64*64 2차원 배열에 0,1 의 값이 무작위로 저장되있습니다.
배열내 1로 저장된 위치들을 사각형범위로 표현하는데 최소의 갯수로 표현하세요. [메모리 사용량용량은 제한이 없습니다. ]
예) 5*5배열일경우
input
01110
01110
01110
00100
output
2
[0,1 , 3,3]
[3,2 , 1,1]
사각형 표현법은 다음과 같음[row,col , height, width]
사각형의 범위는 중첩되도 상관없음
11년 전