seuch10   11달 전

로직은 행과 대각선의 연산 횟수(더하기)를 0~9사이로 고정시킨 후 이때 각 열의 원소값을 최대화하도록 하는 연산 횟수를 찾는 방식입니다.

같은 로직 아래서 최대한 최적화해봤는데 최소 60억번 연산에서 줄어들지 않습니다. 혹시 여기서 어떻게 최적화해야 AC를 받을 수 있을지 아이디어를 제공해주시면 감사하겠습니다.

zenith82114   11달 전

처음 상태가 X인 행에 1번이나 2번 연산을 적절하게 사용해서 만들 수 있는 최대 합을 best[X]라고 합시다. 예를 들어 [8, 2, 1, 1, 4, 0]이라는 행은 [5, 9, 8, 8, 1, 7]로 바꿨을 때 합이 38로 가장 커지므로 best[821140] = 38을 저장합니다. 행의 상태는 000000부터 999999까지이므로 길이가 100만인 배열에 best 값을 모두 전처리해 줍니다.

이제 3번~8번 연산들을 먼저 bruteforce 한 뒤 1번, 2번 연산은 best 배열을 활용해서 고려하면 시간제한 안에 풀 수 있습니다.

seuch10   11달 전

답변 감사합니다. 다만 전처리를 먼저 구현했음에도 시간초과가 나는 건 매한가지네요. 어떤 방식으로 해야 실행 시간이 줄어들지 궁금합니다.

zenith82114   11달 전

Bruteforcing 부분에서 대각선을 열보다 앞으로 순서를 옮겨 보세요. 캐시 히트 측면에서 더 좋아질 수 있습니다.

그래도 시간 초과가 나면 bb를 1차원 배열로 바꿔 보세요. 배열의 차원이 너무 많으면 원소 하나에 접근하는 시간이 유의미하게 증가할 수 있습니다.

seuch10   11달 전

대각선이랑 배열을 일차원으로 바꿔서 최적화했는데도 안되는데 col() 하나 짜르니까 통과됐습니다. 암튼 덕분에 AC 받았습니다. 감사합니다.

zenith82114   11달 전

앗, 제 코드에서도 두 번째 열부터만 했는데 이건 미처 못 봤네요. 애초부터 이것 하나만 했으면 통과했을 거예요. 고생하셨습니다.

댓글을 작성하려면 로그인해야 합니다.