돌고 돌아 기본

프로그래머스 12914번 - 멀리 뛰기 요구사항 1. 한 번에 1칸 또는 2칸을 뛸 수 있을 때, n개의 칸을 건너 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. n개의 칸을 건너 끝에 도달하는 방법의 수를 dp[n]이라고 정의하면 다음과 같습니다. dp[n] = dp[n-2] + dp[n-1] ( n >= 3 ) dp[1] = 1 ( 1칸 ) dp[2] = 2 ( 1칸 + 1칸, 2칸 ) n개의 칸을 건너 끝에 도달하는 경우 마지막에 2칸을 뛰어 끝에 도달하는 경우와, 1칸을 뛰어 끝에 도달하는 경우가 있습니다. 마지막에 2칸을 뛰는 경우는 마지막 2칸을 제외한 n-2 개의 칸을 건너오는 경우의 수이고, 마지막에 1칸을 뛰는 경우는 마지막 1칸을 제..

프로그래머스 12900번 - 2 x n 타일링 요구사항 1. 세로의 길이가 2이고 가로의 길이가 n인 바닥을 타일로 채우는 방법의 수를 반환하라. 2. 타일은 가로길이가 2이고 세로의 길이가 1인 직사각형 모양입니다. 요구사항 분석 및 풀이과정 1. 가로가 n인 바닥을 타일로 채울 수 있는 경우의 수는 마지막 타일을 세로로 배치하는 경우와 가로로 배치하는 경우로 나눌 수 있습니다. 2. 가로가 n인 바닥을 타일로 채울 수 있는 경우의 수를 dp[n]이라고 정의하면 다음과 같습니다. dp[n] = dp[n-2] + dp[n-1] ( n >= 3 ) dp[n-2]는 마지막 타일을 가로로 배치하여 가로의 길이가 2인 타일을 위아래로 2개 배치하는 경우입니다. dp[n-1]는 마지막 타일을 세로로 배치하여 가로..

프로그래머스 43105번 - 정수 삼각형 요구사항 1. 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 최댓값을 반환하라. 2. 단, 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 요구사항 분석 및 풀이과정 1. 주어진 삼각형은 시각적인 표현이고, 삼각형을 배열로 보면 다음과 같습니다. 2. 시각적으로 표현된 삼각형 기준으로 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽이기 때문에, 위 모양을 기준으로는 아래 방향 또는 우측 하단 대각선 방향으로만 이동이 가능합니다. 3. 2번을 경유해오는 칸을 도착하는 칸을 시점으로 보면 왼쪽 상단 대각선 방향 또는 위쪽 방향에서 올 수 있습니다. 그림으로 표현해보면 다음과 같습니다. 4. 3번..

프로그래머스 42898번 - 등굣길 요구사항 1. 물에 잠기지 않은 지역을 통해 학교로 가려고 합니다. 단, 오른쪽과 아래쪽으로만 움직일 수 있습니다. 2. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1, 000, 000, 007로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. 오른쪽과 아래쪽으로만 움직일 수 있다는 뜻은 특정 지역을 기준으로 해당 지역으로 들어오는 방향이 왼쪽과 위쪽밖에 없다는 것을 의미합니다. 2. 따라서 집에서 각 지역까지 갈 수 있는 최단경로의 개수를 dp[지역]이라고 하면 다음과 같습니다. dp[지역] = dp[왼쪽 지역] + dp[위쪽 지역] 3. dp[지역]을 코드로 옮기기 위하여 지역을 좌표 정보로 표현하여 점화식을 정리하면 다음과 같습니다. 단, 집의 위치는..

프로그래머스 12913번 - 땅따먹기 요구사항 1. 1행부터 땅을 밟으며 한 행씩 내려올 때 땅의 점수를 획득합니다. 2. 각 행의 4칸의 땅 중 한 칸만 밟을 수 있으며, 같은 열을 연속해서 밟을 수 없습니다. 3. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라. 요구사항 분석 및 풀이과정 1. 같은 열을 연속해서 밟을 수 없기 때문에, 각 i번째 행의 j번째 칸의 땅에 왔을 때 얻을 수 있는 점수의 최댓값은 다음과 같다. dp[i][j] = i번째 행의 j번째 칸의 땅에 왔을 때 얻을 수 있는 점수의 최댓값 ( 0