본문 바로가기
반응형

dynamicprogramming3

프로그래머스 - 등굣길 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 [1][1]에서 [2][2]로 이동할 수 있는 경우의 수는 (오른쪽으로 이동 -> 아래로 이동), (아래로 이동 -> 오른쪽으로 이동)의 2가지이다. 따라서 점화식을 세워보면 이동할 수 있는 경우의 수는 i가 행, j가 열일 때 DP[i][j] = DP[i-1][j] + DP[i][j-1]로 누적되어 나간다. DP로 더해나갈 .. 2022. 3. 8.
프로그래머스 - 정수 삼각형 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이 간단한 DP 문제이다. 그림에서는 삼각형이지만 실제 배열로 나타내면 [7] [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5] 의 형태이므로 조금 더 점화식을 세우기 쉽다. 누적 값에 현재 값을 더해나가며 DP 배열을 채워나간다 행을 i, 열을 j로 나타내면 [3, 8]에서 3에 더할 수 있는 값은 triangle[i-1][j]에 있는 7이고 8에 더할 수 있는 값은 triangle.. 2022. 3. 6.
프로그래머스 - 땅따먹기 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 문제 풀이 DP를 적용하여 풀면 된다. 주의할 점은 바로 직전의 열이 겹치면 안된다는 것이며 한 행은 항상 4열이다. 따라서, 점화식을 세울 때 해당 행에서 가장 큰 수를 더하되 열이 겹치면 continue해준다. 소스 코드 #include using namespace std; int solution(vector land) { .. 2021. 11. 21.
반응형

티스토리툴바