1932 - c++

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

시행 착오

최근에 다이나믹 프로그래밍 문제를 풀때 테이블이나 재귀식이 새각나지 않는 다면 브루트 포스 또는 모든 것을 다 검사하는 방식으로 코드를 짜보고 거기서 추가 적으로 재귀를 짜라는 식의 설명을 들은 적이 있다.

 

그리하여 나는 일단 DFS를 사용하여 모든 경우의 수를 다 구하였으며, 결과는 시간 초과 였으며 당연한 결과라 생각해 다이내믹 프로그래밍으로 짜보려고 노력했다.

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
int board[501][501];
int sum[501][501];

void dfs(int total, int x, int y){
  if(x >= n || y > x)return;
  if(sum[x][y] < total)sum[x][y] = total;

  dfs(total + board[x+1][y], x+1, y);
  dfs(total + board[x+1][y+1], x+1, y+1);
}

int main(){
  init();
  cin >> n;
  for(int i =0; i < n; ++i)
    for(int j = 0; j <= i; ++j)
      cin >> board[i][j];
  dfs(board[i][j], 0, 0);
  cout << *max_element(sum[n-1], sum[n-1]+n);
  
  return 0;
}

 솔직히 내가 DFS로직을 짜보고 놀랐다....내가 재귀를 쓰다니....

솔직히 이 코드를 짜기 전 까지 재귀에 대한 자신감이 없었는데 이렇게 시도 해보고 성공 해봄으로 써 재귀에 대한 자신감이 조금 뿜뿜 해졌다, 하지만 지금의 문제는 재귀가 아니다.... 테이블을 정의해 보자

 

테이블 정의

어떻게 테이블을 정의 해야 할까 고민이 많았고 그 끝에

두가지 방법을 생각해낸다

 

1. 삼각형을 한층 한층 내려오며 합을 구하고 저장한다.

2. 아래에서 부터 올라오며 한번한번 다 구한다.

 

 

2번이 아니라는 건 확실하다 DFS랑 다를게 없다

가장 답에 가까운건 1번이라 생각했지만 대체 어떻게 이걸 정의 해야 할지 감이 잡히지 않았다.

그리고 답을 보았다.

 

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
int board[501][501];
int d[501][501];

int main(){
  init();
  cin >> n;
  for(int i =1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      cin >> board[i][j];
  
  d[1][1] = board[1][1];
  for(int i = 2; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      d[i][j] = max(d[i-1][j-1], d[i-1][j]) + board[i][j];

  cout << *max_element(d[n]+1, d[n]+n+1);
  
  return 0;
}

한줄 한줄 버릴것이 없이 모두 각자의 이유가 있는 코드 였다, 정말 예뻤다.

---

# WHY (1)

왜 입력을 받을 때 1번 행의 1번 열부터 입력을 받았을 까?

for(int i =1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      cin >> board[i][j];

조금 뒤에 합을 구하는 로직을 보면 알 수 있으니 일단 

그저 인덱스 계산을 편하게 하기 위해서만이 아니라는 것을 알고만 넘어 가보자.

 

#WHY (2)

왜 이렇게 계산 한 걸까?

for(int i = 2; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      d[i][j] = max(d[i-1][j-1], d[i-1][j]) + board[i][j];

현재 나의 위치에서 왼쪽 위, 오른쪽 위를 조사한후 최댓값을 찾아 더한다.

여기서 WHY(1)의 물음이 해결 된다. 밑의 그림을 보자

알겠는가?? 오히려 더 이해하기 어려울 수도 있느나 열심히 그렸다...

여기서 얻어 가길 바라는건 만약 왼쪽의 0이 없었다면 에러가 날 수도 있는 것이다.

물론 zero-index 부터 시작해도 따로 처리해도 되는 부분 이겠지만 one-index 부터 시작하면서 처리하기 편해진 것은 자명한 사실이니 배워 가는 것이 좋겠다!

이런게 설계구나....

---

문제를 풀며 

요즘 문제를 풀며 답에 대한 의존도가 너무 높아지고 있어 걱정이다. 나름 고민을 한다고는 하나 이렇게 풀어 나가는 것이 맞는 것인가 고민이 많다.

 

예전에 본 알고리즘 강의 글 에서 쉬운 문제는 1시간 고민하고 안되면 답을 보면서 이해하라 라는 문장을 보고 지금 까지 그렇게 해왔으며 실력또한 정말 많이 길러졌고 여러 아이디어들을 배울 수 있었다.

그런데 요즘 읽고 있는 황농문 교수 님의 슬로싱킹이라는 책에서는 창의성을 높이기 위해서는 계속 몰입하고 고민하는 것이라고 말씀 하셨다.

 

이렇게 답을 보면서 아이디어만 얻어 가는게 과연 중요한 걸까? 나중에는 미지의 문제들을 나 혼자의 힘으로 풀어야 하는데 내가 못 버티면 어떡하지 라는 생각이 문득 들었다....

 

인생은 길다 치고 문제들을 천천히 생각하는 연습을 할 것인가?

아니면 아이디어만 얻어가며 실력을 향상 시키는 것이 좋을까?

 

무엇 인가 하나를 끝까지 잡고 늘어져 본적 없는 나에게는 너무 어려운 고민이지만 한번 쯤은 무조건 해봐야 하는 고민인 것 같아 이렇게 글로 남겨 본다.