[2주차_금요일] 12913_땅따먹기

[baexxbin]

• 사이트: 프로그래머스
• 문제: 땅따먹기
• 번호: 12913
• 레벨: Level2

[icegosimperson]

🤔 시간복잡도 고려사항 N <= 100,000, 행렬 크기가 크지 않음 44 O(N 4 * 4) = O(N)

💡 풀이 아이디어 이전 행에서 계산한 값에 의존 : DP

        for(int i=1; i<land.length; i++){
            for(int j=0; j<4; j++){
                int max = 0;
                for(int k=0; k<4; k++){
                    if(k != j) { // 이전 열과 같은 열이 아닐 때
                        max = Math.max(max, land[i-1][k]);
                    }
                }
                land[i][j] += max;
            }
        }

[KodaHye]

🤔 시간복잡도 고려사항

• 주어진 배열 탐색해도 괜찮음
• 행의 개수: N <= 100,000, 열의 개수 4
• N * 4 <= 400,000

💡 풀이 아이디어

• 행을 기준으로 반복문 실행 후 열에 대해 반복문 실행하며 탐색
• 현재 지점 기준으로 이전 행에서 같은 열 번호라면 continue
• dp[r][c]: (r, c)에서 얻을 수 있는 최대값 저장

[baexxbin]

🤔 시간복잡도 고려사항

• 행(N) <= 100,000
• 열 = 4
• 4*100,000 → O(NlogN)

💡 풀이 아이디어

• 초기 아이디어

  • dp[i][j] = k, i번째행에서 j번열을 못밟을때 최대값 미리 초기화해놓음
  • 그 후, dfs돌며 상황별 dp값 더해주기

    이전에 밟지 못하는 값을 알 수 없음..

• 새로운 아이디어

  • dp[i][j]: i행에서 j열 밟을때 최대값, (현재 land값 + Max(이전 열에서 못밟는거 제외 최대값)

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100,000 → 10^5이므로 O(nlogn)

💡 풀이 아이디어

• DP방식으로 현재 칸의 인덱스 외의 칸들 중에서 최댓값을 계속 더해줌

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 100,000

• 완전탐색(DFS, BFS)로 풀려면, O(N^2)이므로 시간초과

• DP를 활용 => O(N44)로 해결 가능

• 💡 풀이 아이디어

• 현재 land[i][j]일 때, 이전 행인 land[i-1]에서 j열과 같지 않은 것을 골라 합했을 때 최댓값을 갱신

• 점화식

  dp[i][j] = max(dp[i][j], dp[i-1][k])  // j != k

bfs,dfs 탐색 시간복잡도가 O(N*E)인 줄알고 시간초과가 나는 이유를 몰랐습니다... 다시보니 N이 충분히 크고 dp로 풀면 될 것 같았습니다

[yeahdy]

🤔 시간복잡도 고려사항 알고리즘: 일반구현 O(n) 시간복잡도: N <= 100,000 크기로 O(NlogN)까지 가능

💡 풀이 아이디어 요구사항은 이전의 행과 같은 열을 밝지 않고, 각 행의 열의 합이 최고점 찾기 이전의 행과 현재의 행을 비교하는데, 이전 행의 열들 중 현재 행과 같은 열을 제외하고 최고점을 찾는다