DP

문제 설명 현대모비스에서 개발한 실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t21)를 유지할 수 있도록 합니다. 현재(0분) 실내온도는 실외온도와 같습니다. 실내공조 제어 시스템은 실내온도를 조절하기 위해 에어컨의 전원을 켜 희망온도를 설정합니다. 희망온도는 에어컨의 전원이 켜져 있는 동안 원하는 값으로 변경할 수 있습니다. 실내온도와 희망온도가 다르다면 1분 뒤 실내온도가 희망온도와 같아지는 방향으로 1도 상승 또는 하강합니다. 실내온도가 희망온도와 같다면 에어컨이 켜져 있는 동안은 실내온도가 변하지 않습니다. 에어컨의 전원을 끄면 실내온도가 실외온도와 같아지는 방향으로 매 분 1도 상승 또는 하강합니다. 실내온도와 실외온도가 같다면 실내온도는 변하지 않습니다. ..

DP 제일 위에 있는 문제를 풀어보았다. 3kg과 5kg의 설탕으로 목표 무게를 만드는 것이다. 만들지 못하면 -1을 만들 수 있으면, 최소한의 수의 설탕으로 목표 무게를 만드는 것이다. 메모제이션을 이용하여 0부터 목표 무게까지 최소한의 수를 쌓아가면 된다. 0 = -1 1 = -1 2 = -1 3 = 1 4 = -1 5 = 1 은 기저 조건으로 설정한다. 만약 기저 조건보다 낮은 목표 무게가 있다면 예외 처리를 한다. 그리고, 이제 무게를 6부터 쌓아갈 때 3을 뺀 수와 5를 뺀 무게 중, 적은 수의 설탕 봉지를 쓴 경우를 택해 1을 더하면 된다. 또한, 15같은 무게는 3kg으로도 5kg으로도 만들 수 있다. 이런 경우를 생각해 3kg을 쓴 경우와 5kg을 쓴 경우 모두를 생각해 비교해야 한다. 다..

DP문제에 전형적인 풀이 방법인 메모제이션을 이용하여 문제를 풀었다. 처음에는 어떤 식으로 문제를 풀어 나가야 할지 감이 잡히지 않았다. 계속 생각한 결과 한가지만 주의하면 된다는 생각을 하게 되었다. 이웃한 집만 같은 색깔이 아니면 되기 때문에 하나의 집을 임의의 색으로 칠하면 다음 집에서는 선택할 수 있는 경우가 2가지로 좁혀지고, 그다음은 여전히 2가지의 선택의 경우가 생긴다. 즉, 소모 값들을 배열에 저장한다 생각하면, 같은 column에 있는 값만 선택하지 않으면 된다. 그렇다면 이제 index문제만 해결하면 문제는 풀린다. R은 [0]에, G는 [1]에, B는 [2]에 저장한다 하자. 2번 index의 요소를 처리한다 했을때, 0과 1에 접근할 수 있는 방법을 찾으면 된다. 링 버퍼의 개념을 ..

오랜만에 DP 문제를 풀어보았다. 정수 삼각형을 입력받아 저장한 뒤, 최종적으로 가장 큰 수를 만들어 가는 문제이다. 단, 선택할 수는 다음행의 수 중, 왼쪽, 오른쪽 둘 중 하나만 선택 가능하다. 즉, 7에서 선택할 수 있는 수는 3, 8 둘 중 하나이다. 이런 방식으로 하나씩 더해 나가 가장 큰 수를 만들면 된다. 얼핏 보면, 선택할 수 있는 수 중에 큰 수를 선택해서 진행하면 되는 탐욕 법 문제로 볼 수 있다. 하지만, 그 다음 상황은 모르기 때문에 탐욕 법은 항상 올바른 답을 주지 않는다. 따라서, 동적 계획법을 이용하여 답을 구해내면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Triangle { public static voi..

두 수열이 주어졌을 때, 가장 긴 공통 수열을 찾아내는 문제이다. 앞서 풀었던 가장 긴 증가하는 부분 수열과 비슷하다고 생각할 수 있지만 조금 다른 문제이다. for문을 여러 번 돌려 메모제이션을 이용하여 문제를 풀려했었다. 하지만, 문자열을 계속해서 반복하고 어디까지 일치하는지를 기록해야 하고, 건너뛰는 요소가 있을 수 있기 때문에 쉽지 않았다. 해답은 2차원 배열을 이용한 메모제이션이였다. 입력받은 두 문자열 길이보다 1씩 큰 2차원 배열을 생성한 뒤, 0번째 column과 0번째 row을 0으로 초기화 한 뒤, 문제를 풀어나가면 된다. 0으로 채우는 이유는 기저 조건을 설정하는 것이다. 2중 for문을 이용하여 row와 column의 각 요소들을 비교하며 진행한다. 그러다 일치하는 요소가 발견되면,..