[21주차_화요일] 로봇 조종하기

[KodaHye]

• 사이트: 백준(BOJ)
• 문제: 로봇 조종하기
• 번호: 2169

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 1≤ 행의 크기(N), 열의 크기(M) ≤1,000
• 로봇이 갈 수 있는 모든 경로를 고려한다면,,, 방문한 곳을 다시 못가는 것을 고려해도 2 ^ 100,000 정도가 될 수 있음
• 2차원 DP를 통해 풀이: N × (3 × M)

💡 풀이 아이디어

2차원 DP 배열을 통해 (r, c)지점에 도달 했을 때, 가능한 최대 가치 구하기

변수	설명
final int INF	DP 배열을 초기화하는 값 각 배열의 값은 절대값이 100을 넘지 않는 정수이기 때문에, 가능한 가치 합의 최소값으로 설정해줌 1_000 × 1_000 × (-100)
int[][] arr	원본 배열
int[][][] dp	위, 왼쪽, 오른쪽에서 오는 경우를 나누어서 올 때, (r, c)에서 얻을 수 있는 가치의 최대값 [0]: 왼쪽에서 오는 경우 [1]: 위에서 오는 경우 [2]: 오른쪽에서 오는 경우

1. arr 정보 입력받기
2. dp 테이블 채우기

for(int r = 1; r < dp[0].length; r++) {
        // 첫번째 행은 오른쪽으로만 갈 수 있음
	if(r == 1) {
		dp[0][r][0] = 0;
		for(int c = 1; c < dp[0][0].length; c++) {
			dp[0][r][c] = arr[r][c] + dp[0][r][c - 1];
		}
		continue;
	}
	
	// 위에서 오는 경우
	for(int c = 1; c < dp[0][0].length; c++) {
		dp[1][r][c] = Math.max(dp[0][r - 1][c], Math.max(dp[1][r - 1][c], dp[2][r - 1][c])) + arr[r][c];
	}

	// 왼쪽에서 오는 경우
        // dp[2][r][c - 1]은 (r, c) 에서 왼쪽으로 가서 (r, c - 1)이 된 것이기 때문에, 고려 X
	for(int c = 1; c < dp[0][0].length; c++) {
		dp[0][r][c] = Math.max(dp[0][r][c - 1], dp[1][r][c - 1]) + arr[r][c];
	}
	
	// 오른쪽에서 오는 경우
        // dp[1][r][c + 1]은 (r, c) 지점에서 오른쪽으로 가서 (r, c + 1)가 된 것이기 때문에, 고려 X
	for(int c = dp[0][0].length - 2; c > 0; c--) {
		dp[2][r][c] = Math.max(dp[1][r][c + 1], dp[2][r][c + 1]) + arr[r][c];
	}
	
	
}

[jewan100]

🤔 시간복잡도 고려사항

• 1≤N, M≤1,000
• 100 층마다 숫자 1개 선택 → 좌, 우로 최댓값 확인 → TLE거나 비효율적
• DP의 메모이제이션을 이용 → 누적합

💡 풀이 아이디어

• 로봇은 해당 층에서 한 방향(좌, 우)으로 밖에 못 움직임 → 방문한 곳은 방문하지 않음

  • 첫 시작은 오른쪽으로만 이동

• 각 층마다 오른쪽으로 누적합, 왼쪽으로 누적합을 구해서, 구하고자 하는 값에서 가질 수 있는 최댓값으로 갱신
  

  변수	설명
  int[][] dp	메모이제이션 2차원 배열
  dp[0]	최댓값 저장할 배열
  dp[1]	오른쪽으로 누적합
  dp[2]	왼쪽으로 누적합

• 초기화

int[][] dp = new int[3][m];
dp[0][0] = arr[0][0];
for (int i = 1; i < m; i++)
    dp[0][i] = dp[0][i - 1] + arr[0][i]; // 1층은 오른쪽 누적합

• DP 계산

for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++)
        dp[1][j] = dp[2][j] = dp[0][j] + arr[i][j]; // 아래로 내려오는 것은 디폴트
    for (int j = 1; j < m; j++)
        dp[1][j] = Math.max(dp[1][j], dp[1][j - 1] + arr[i][j]); // 오른쪽 누적합을 이용해 최댓값 갱신
    for (int j = m - 2; j >= 0; j--)
        dp[2][j] = Math.max(dp[2][j], dp[2][j + 1] + arr[i][j]); // 왼쪽 누적합을 이용해 최댓값 갱신
    for (int j = 0; j < m; j++)
        dp[0][j] = Math.max(dp[1][j], dp[2][j]); // 두 누적합의 최댓값을 가져와 갱신
}

[baexxbin]

🤔 시간복잡도 고려사항

• 1≤N, M≤1,000
• N*M (10^6) : dp배열을 이용했을 경우
• 재귀를 통한 완전탐색 진행 시 : 3^(N+M)
  • 각 위치마다 최대 3개의 경로 탐색
  • 시간 초과

💡 풀이 아이디어

• DP이용
  • 로봇의 움직임이 정해져 있음, 한번 방문한 곳은 방문 불가
  • dp 초기화 (0행)
    • 왼쪽 → 오른쪽 방향으로만 이동 가능
      • (0,0)에서 시작하고, 위, 오른쪽에서 올 수 없음

        // 첫번째 행 초기화
      dp[0][0] = board[0][0];
      for (int j = 1; j < M; j++) {       // 오른쪽으로만 탐색 가능(이미 지나온 길 탐색 불가)
          dp[0][j] = board[0][j] + dp[0][j - 1];
      }

  • 점화식 구성
    • 오른쪽, 왼쪽에서 오는 각 경우 구하기
      • 오른쪽(왼쪽)에서 오는 경우, 위에서 오는 경우 중 큰 값에 현재 값 더하기
    • 오른쪽, 왼쪽 각 경우의 수 구한 후, 두 경우 중 큰 값 구하기

    for (int i = 1; i < N; i++) {
           int[] left = new int[M];
           int[] right = new int[M];
    
           left[0] = dp[i - 1][0] + board[i][0];   // 0번째열은 일단 이전 행에서 아래로 내려와야함 (위에서 내려오는 한가지 경우)
           for (int j = 1; j < M; j++) {           // 왼쪽에서 오는거, 위에서 내려오는 두가지 경우
               left[j] = Math.max(left[j - 1], dp[i - 1][j]) + board[i][j];
           }
    
           right[M-1] = dp[i- 1][M-1] + board[i][M-1];
           for (int j = M - 2; j >= 0; j--) {
               right[j] = Math.max(right[j+1], dp[i-1][j]) + board[i][j];
           }
    
           // 왼쪽 오른쪽 값 합침
           for (int j = 0; j < M; j++) {
               dp[i][j] = Math.max(left[j], right[j]);
           }
       }

[yeongleej]

🤔 시간복잡도 고려사항

• N, M <= 1000
• 갈 수 있는 방향 : 3

=> 완전탐색 : O(3^(N * M)) 은 시간초과
=> DP로 최적의 루트 찾으면서 진행 : O(N * M)

💡 풀이 아이디어

• dp[i][j] : (i, j)에 도달하는 최대 가치

  • (i, j)에서 갈 수 있는 방향은 (하, 좌, 우)
  • dp[i][j] = g[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i][j+1])

• dp 초기화

  • (1,1)에서 시작하므로 첫 행은 좌 ->우로만 이동할 수 있음

  for(int j=1; j<M+1; j++) {
  	dp[1][j] = dp[1][j-1] + g[1][j];
  }

• 위에서 오는 경우, 좌 -> 우로 가는 경우 중 큰 값 계산

  		t1[1] = dp[i-1][1] + g[i][1];
  		for(int j=2; j<M+1; j++) {
  			t1[j] = Math.max(dp[i-1][j], t1[j-1]) + g[i][j];
  		}

• 위에서 오는 경우, '우 -> 좌'로 가는 경우 중 큰 값 계산

  		t2[M] = dp[i-1][M] + g[i][M]; 
  		for(int j=M-1; j>=0; j--) {
  			t2[j] = Math.max(dp[i-1][j], t2[j+1]) + g[i][j];
  		}

• 위의 두 경우 중 더 큰값이 최적의 경로