Better Than Yesterday

1) 2차원 배열을 이용해서 트리구조를 만들어보자. 2) 어떤 규칙인가 최대값들을 배열들이 저장하고 있으면 편하겠다. -> DP arr[4][2]기준으로 생각해보자. 7은 왼쪽 대각선 위의 8을 받을수도 오른쪽 대각선 위의 1을 받을 수도 있다. 둘 중 큰 놈을 받으면 되는데, 확실한 건 7이 받을 수 있는 놈은 두놈 중 큰 한놈 뿐이다. 이를 식으로 나타내보면 arr[i][j] = max(arr[i-1][j-1], arr[i-1][j]) + arr[i][j] 이다. 여기서는 초기값 필요없는게 arr[1][1]이 처음 값인데 arr[0][0]이 모두 0으로 초기화 되어있어서 따로 초기값 필요없이 바로 찾아 나가면 된다. 트리구조는 2차원 배열로 만들면 되고, 가장 왼쪽이나, 가장 오른쪽에 위치한 놈들은 ..

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..