반폭문의 형태만 봐도, O(n^2 * r) 이네요.

r번의 루프를 도는데 그 때마다 n*n번 안쪽 루프를 도니까 n^2 * r이죠.

문제는 저도 안 풀어봐서 얼마를 목표로 해야 하는지는 모르겠지만, 그렇게 간단히 루프 중첩으로 해결될 건 아닌 것 같습니다.

코드속의 n은 제가 정의한 n 이고 빅오표기법으로는 반복문의 중첩 개수에 따라서 달라지는거 아닌가요?? 제코드에는 반복문 중첩이 없어서 O(r*n)아닌가요 ? 이건 잘 몰라서 그러는데 입력할때 쓰는 반복문도 빅오표기법에 들어가는건가요 ?? 그럼 O(2n*r)이지 않나요 ?

빅오 표기법은 변수의 값에 따라 시간이 얼마나 점근적으로 변하는지를 보는 겁니다.

쉽게 예를 들어서, n이 100이면 n*n은 10000이고, n이 10000이면 n*n은 1억이고, 반목문을 1억회 도는 건 1만회 도는 것보다 1만 배 시간이 더 걸리죠. O(n)이라면 100배가 더 걸려야 하는데, 만 배가 더 걸리는 건 시간복잡도가 O(n^2)이기 때문입니다.

이 문제에서 변수는 n과 r이고, 바깥 루프는 무조건 r번 돌지만 안쪽 루프는 n번이 아니라 n^2번 돌게 됩니다. 이게 중요한 것이지, n에 대한 루프라는 사실 자체가 중요한 게 아닙니다.

마찬가지로 초기화를 하는 부분도 n^2번 도니까 O(n^2)이 되는데, 그럼 합계 O (rn^2 + n^2)이 아니냐고 하실 수도 있는데, rn^2이 n^2보다 점근적으로 빠르게 증가하기 때문에 별도로 표기할 필요가 없습니다.

더 좋은 알고리즘도 있을지 모르겠지만, 일단 이 문제에서 요구하는 건 O(N^2 + M) 정도 되는 것 같습니다. 자바의 시간 보너스 때문에 O(N^2 + NM) 까지도 성공은 하는 모양이네요.

M이 의미하는게 뭔가요??

문제에 있는 M입니다. r 이라고 쓰신 그거요.