NHN 4번 O(n)으로 푼사람 이 테케 설명좀해주라

[익명(220.79)]

{ 1, 1, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1 }, 2, 5

답 73

첫번째에 지고 두번째부터 전승하면 73나옴

이거 처음 1,1,1 연승할떄 6 계산하고

10 만나서 연승 깨질때

3연패로 처리해서 15더하고 10부터 시작하면 62 나와서 틀린 풀이고

1패만 처리해서 5 더하고 2번째 1부터 다시 시작하면 O(n^2) 되는거 아님??

[익명(221.167)]

연승 잘하다가 패배되면 처음에 패배됐을 경우는 무시해 그다음에 바로 패배 됐다면 아까 올려놓은 계산값을 비교하고 인덱스 차이를 좀 벌렸다면 맨 처음에 연승하고 나중에 패배한 것을 맨 처음에 패배하고 나중에 연승한 것이랑 다름이 없어서 이걸 비교하면 됨 그니까 값이 똑같은지 아닌지 비교하면 돼 이게 O(N)인데

[익명(220.79)]

진짜 뭔말인지 하나도 이해 안감 저 예제 기준으로 설명좀. 10 만났을때 연승 깨지는걸 무시한다는거임?

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(220.79)]

첫번째 지면 7되고 2번쨰부터 전승하면 11개라서 +66임

[만두만둘(106.101)]

너 합격연락옴??