밤이 블로그

BOJ#2252 줄 세우기 * 문제https://www.acmicpc.net/problem/2252 * 풀이 어떤 일에 선/후 관계나 순서가 있으므로 위상 정렬을 이용해보았습니다. -> 위상 정렬 설명 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824 주의할 점으로는32000 * 32000 배열이 선언이 안되므로 (Heap 사이즈)ArrayList를 사용했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232252_Lineup/src import java.io.*; import java.util.*; /** * BOJ#2252 줄세우기 * https://www.acmic..

BOJ#1932 숫자삼각형 * 문제https://www.acmicpc.net/problem/1932 * 풀이 ▷ dp 정의dp[i][j] : i층에서 j 를 선택했을 때, 0~i 층의 최대값 ▷ dp 점화식dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1]) 별로 어렵지 않은 문제였지만 시간초과로 고생을 좀 했습니다. 원인으로는 dp 초기값을 0으로 설정했는데 코드 64라인에서 dp값을 재활용 할 때, 원래 삼각형 값이 0인 경우와 dp 초기값 0인 경우를 구분하지 못해서 메모이제이션을 하지 못했기 때문입니다. dp 초기값을 -1으로 고쳐서 해결하였습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/..

BOJ#1149 RGB거리* 문제https://www.acmicpc.net/problem/1149 * 풀이 ▷ 규칙 - 각 집은 R, G, B 3가지 색 중 한가지 색으로 칠한다. - 이웃한 집은 같은 색으로 칠하지 않는다. - 마지막 집은 R, G, B 3가지 색 중 하나이다. - 위 3가지 경우 중 최소값이 우리가 원하는 정답이다. ▷ dp 정의dp[i][RED] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 RED일 때 costdp[i][GREEN] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 GREEN일 때 costdp[i][BLUE] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 BLUE일 때 cost ▷ 점화식dp[i][RED] = min(dp[i-1][GREEN], dp[i..