1 0 0 0 2 9 0 0 3 10 8 0 4 5 6 7 문제 이해 소용돌이 문제와 유사하다. 실제로는 2차원 배열로 넣었을때 위와 같은 모양을 띈다. x 증가 -> x의 끝 도달 -> y 증가 -> y의 끝 도달 -> x 감소 y 감소 이런식의 반복이 이루어진다. bfs 방식으로 방문했는지 안했는지를 값이 0이냐 아니냐로 비교하였다. 방문여부 || x, y 좌표의 위치에 따라 dir값 (0 - 왼쪽 대각선 아래, 1 - 오른쪽, 2 - 왼쪽 대각선 위) 세팅해준다. 배열의 총 개수는 순차수열로 생성하였고 배열의 개수만큼 num이 증가하면 while문을 나오게 만들었다. import java.util.*; class Solution { public int[] solution(int n) { int[][..

문제 이해 삼각형의 꼭대기에서 바닥까지 이어오는 경로중 숫자의 합이 가장 큰 경우를 찾아라 이 문제의 경우 이어지는 경로라고 되어있다. 아래로 내려갈때 대각선 방향의 왼쪽 오른쪽으로만 이동 가능하다. DP로 문제를 해결하고자 했다. 문제와는 다르게 반대로 아래에서 위로 왼쪽 오른쪽을 각자 더했을때 더 큰 숫자를 배열에 남기기로 했다. 아래에서 위로 비교할때 index가 0보다 작을 경우를 체크하면서 값을 채워나가게 했다. import java.util.*; class Solution { public int solution(int[][] triangle) { int answer = 0; int[][] dp = new int[triangle.length+1][triangle.length]; for(int i..

문제 이해 한 행씩 내려가면서 땅따먹는다. 점수 최대로 나오게 땅을 따먹어라 한 행씩 내려올 때 같은 열을 연속으로 밟을 수 없다. 예제에는 안나왔지만 같은 행에 같은 점수가 나올수 있고 그 점수가 최대값일수 있다고 생각해야한다. 한 행씩 내려오면서 연속된 열 제외 위 아래 열의 값을 더하여 dp[i][j] 에 나올 수 있는 max값을 배치한다. 마지막 행에 나오는 점수중 max값이 땅따먹기에서 나올 수 있는 최대의 점수이다. import java.util.*; class Solution { int solution(int[][] land) { int answer = 0; // 0행은 [0,0,0,0] int[][] dp = new int[land.length+1][4]; for(int i = 1; i