목록배열 돌리기 5 (1)

개발 쥬스

[백준/Java] 17470 배열 돌리기 5

🔗 문제 링크: https://www.acmicpc.net/problem/17470 🔍 해결 과정배열 돌리기 3 문제와 내용은 같으나 연산의 수 R의 최댓값이 200만이라는 점에서 차이가 있습니다.직접 배열의 내용 자체를 가지고 연산을 활용하기에는 시간복잡도 O(NMR)을 가지기 때문에 최악의 경우 200만 x 10000 = 200억의 연산이 진행이 되기에 일반적인 풀이로는 시간초과가 발생합니다. 그래서 처음에는 배열의 내용들을 바탕으로 연산하기보다는 배열의 영역을 매핑하여 압축시키고 이를 바탕으로 연산을 진행해야겠다는 생각을 했습니다. 즉 그림으로 표현하자면 다음과 같습니다.  위 네 가지의 영역을 바탕으로 2 x 2 압축된 배열을 만들고 R번 연산을 진행을 하게 된다면 최대 2 X 2 X 200만..
카테고리 없음 2025. 1. 5. 13:49
이전 Prev 1 Next 다음