-
Java 1149 RGB거리PS 2023. 5. 13. 00:23
풀이 :
같은 색깔의 집이 연속하면 안된다는 조건만 잘 지키면 어렵지 않게 풀 수 있는 문제였습니다.
그리고 처음 시작하는 경우가 3가지 있기 때문에 각각의 시작점에서 구한 최소값들을 비교하여 그 중에서 제일 작은 값을 출력하면 됩니다.
dp문제이기에 메모이제이션을 할 배열을 선언하고 최종값에 도달하기 전까지의 값들을 저장해주며 연산을 이어나가면 됩니다.
dp문제를 풀 때는 내가 당장 어떤 조건문이나 반복문을 통해 원하는 값을 한방에 도출해낸다는 생각보단 내가 원하는 값들을 도출할 수 있는 식을 세워서 그 식들이 내가 원하는 값을 구해준단 생각을 가지고 접근하는 게 중요하고 dp 문제가 어려우신 분이라면 제일 중요한 건 많이 풀어봐야 감을 잡을 수 있습니다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] house = new int[n][3]; int[][] dp = new int[n][3]; StringTokenizer st; for(int i = 0; i < n; i++){ st = new StringTokenizer(br.readLine(), " "); house[i][0] = Integer.parseInt(st.nextToken()); house[i][1] = Integer.parseInt(st.nextToken()); house[i][2] = Integer.parseInt(st.nextToken()); } dp[0][0] = house[0][0]; dp[0][1] = house[0][1]; dp[0][2] = house[0][2]; for(int i = 1; i < n; i++){ dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + house[i][0]; dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + house[i][1]; dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + house[i][2]; } int result = Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2])); System.out.println(result); } }
'PS' 카테고리의 다른 글
Java 1021 회전하는 큐 (0) 2023.05.22 Java 9461 파도반 수열 (0) 2023.05.22 Java 1145 적어도 대부분의 배수 (0) 2023.05.11 Java 2941 크로아티아 알파벳 (0) 2023.05.06 Java 1929 소수 구하기 (0) 2023.05.05