RGB๊ฑฐ๋ฆฌ์๋ ์ง์ด N๊ฐ ์๋ค. ๊ฑฐ๋ฆฌ๋ ์ ๋ถ์ผ๋ก ๋ํ๋ผ ์ ์๊ณ , 1๋ฒ ์ง๋ถํฐ N๋ฒ ์ง์ด ์์๋๋ก ์๋ค.
์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋ ์ค ํ๋์ ์์ผ๋ก ์น ํด์ผ ํ๋ค. ๊ฐ๊ฐ์ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด ์ฃผ์ด์ก์ ๋, ์๋ ๊ท์น์ ๋ง์กฑํ๋ฉด์ ๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ์ ๊ตฌํด๋ณด์.
- 1๋ฒ ์ง์ ์์ 2๋ฒ ์ง์ ์๊ณผ ๊ฐ์ง ์์์ผ ํ๋ค.
- N๋ฒ ์ง์ ์์ N-1๋ฒ ์ง์ ์๊ณผ ๊ฐ์ง ์์์ผ ํ๋ค.
- i(2 โค i โค N-1)๋ฒ ์ง์ ์์ i-1๋ฒ, i+1๋ฒ ์ง์ ์๊ณผ ๊ฐ์ง ์์์ผ ํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ง์ ์ N(2 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด 1๋ฒ ์ง๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ง์ ์น ํ๋ ๋น์ฉ์ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
๐ก ๊ฐ ์ง์ด ๋นจ๊ฐ, ์ด๋ก, ํ๋์ธ ๊ฒฝ์ฐ ๋ชจ๋ ๊ณ ๋ คํ๋ฉฐ, ์ด์ ์ ์๊ณผ ๊ฐ์ง ์์ ์์ ์ฐพ์
for(int i=1; i<n; i++) {
cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]);
cost[i][1] += Math.min(cost[i-1][0], cost[i-1][2]);
cost[i][2] += Math.min(cost[i-1][0], cost[i-1][1]);
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
public class DP_14 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] cost = new int[n][3];
int[][] dp = new int[n][3];
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
for(int j=0; j<3; j++) {
cost[i][j] = Integer.parseInt(s[j]);
}
}
for(int i=1; i<n; i++) {
cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]);
cost[i][1] += Math.min(cost[i-1][0], cost[i-1][2]);
cost[i][2] += Math.min(cost[i-1][0], cost[i-1][1]);
}
bw.write(Math.min(Math.min(cost[n-1][0], cost[n-1][1]), cost[n-1][2])+"");
bw.flush();
bw.close();
}
}
์ฑ๊ณตโจ