[Week 1] TRIANGLEPATH self review - yujungee

[yujungee]

TRIANGLEPATH self review

• 파일명: algo_2022/TRIANGLEPATH.cpp (branch - yujungee)
• 수행시간: 32ms

1. 문제 해결 과정

맞게 해놓고 x랑 y 좌표를 거꾸로 받아서 계속 고민한 문제
파라미터가 아니라 입력받을 때 y, x 로 받았어야 하는데 실수를 했다.
나머지는 다른 dp문제 처럼 풀었고 cache = 좌표 안의 숫자 + max(바로 아래 숫자, 오른쪽 아래 숫자) 를 통해 큰 수를 누적하도록 했다.

2. 아이디어

• dp, 메모이제이션

3. 코드 설명

• 재귀와 메모이제이션을 통해 구현한 함수

  int solve(int x, int y){
      
      if (x>=n || y >=n) return 0;    // 범위를 넘어갔을 때 (x, y 둘다 증가하므로 0보다 작은 경우는 생략)
      
     // 풀지 않은 문제
      else if (cache[x][y] <= 0) return cache[x][y] = triangle[x][y] + max(solve(x,y+1), solve(x+1, y+1));
      
     // 이미 푼 문제면 리턴 
      return cache[x][y];
  }

• main 함수

  int main(){
      int tc;
      cin >> tc;
      
      while (tc--) {
          cin >> n;
          memset(cache, 0, sizeof(cache));
          for (int i=0; i<n; i++) {
              for (int j=0; j<=i; j++) {
                  cin >> triangle[j][i];    // x(=i)가 열, y(=j)가 행
              }
          }
          
          cout << solve(0,0) << endl;
      }
  
      
  }