[프로그래머스] LV3. 산 모양 타일링 문제 풀이

문제 풀이고려해야할 점더보기타일은 위와 아래로 존재하고 있다. 이 문제는 위와 아래 타일에 각각의 경우에 따른 계산이 필요하다.  n의 최대 개수는 100,000 이므로 모든 경우의 수를 완전 탐색할 경우 시간 초과 문제가 발생한다.  풀이 아이디어 더보기다이나믹 프로그래밍타일의 개수에 따른 점화식을 세워 계산한다. 이때 점화식은 위 타일 아래 타일 분리하여 계산하여야 한다.  점화식 계산 DP 배열은 2차원으로 생성. int[][] dp = new int[n+1][2]; 형식으로 선언하였다. 이때 배열의 첫 번째 인덱스는 몇 번째 타일인지를 나타내고 두 번째 인덱스는 위 타일인지 아래타일인지를 나타낸다. 이 코드에서는 위의 인덱스를 0으로 아래를 1로 표시한다. 아래 타일 점화식아래 타일(dp[n][1..
알고리즘/코딩테스트 2024. 12. 9. 16:29
1