Heecheol's blog

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 당연하게 반복문을 통해 하나씩 더해서 출력하는건 시간초과가 난다. dp문제인 것을 알기때문에 그 방향으로 접근해보면, result[k]는 k번째까지의 수를 더한 값이다. a번째 수부터 b번째 수까지 전부 더한다면 a + (a + 1) ...+ b - 1+ b 이렇게 될 것이다. 이것을 통해 식을 생각해보면 a번째 수부터 b번째 수까지 더한 값은 result[b] ..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n에 따라서 가로 길이가 1씩 늘어난다. 가로가 k라고 가정하고 맨 왼쪽에 가로가 1인 블럭을 둔다고 생각하자. 이렇게되면 나머지에는 가로가 k-1이고 세로가 2인 공간이 남는다. result[k]가 가로가 k일때 블럭을 채워넣는 경우의 수라고 한다면 맨 왼쪽에 1짜리를 두면 남은 공간엔 result[k - 1]의 결과가 들어갈 것이다. 다음으로, 맨 왼쪽에 가로가 2인 블럭을 두게되면 당연하게 아래에도 가..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 처음으로 직접 점화식을 찾고 한 번에 맞췄다. 테이블을 정의하는게 중요한 것 같은데, 나는 문제에서 필요한 것들을 토대로 접근했다. 우선, 문제에서 요구하는 답인 집을 칠하는 비용의 최소값 정보를 가지고 있어야한다고 생각했다. 또한, 비용을 구할땐 이웃한 집의 색이 달라야한다고 생각했기때문에 색에 대한 정보도 필요하다고 생각해서 result배열을 2차원으로 잡았다...

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 아 점화식 구하는게 너무 어렵다. result변수를 1차원으로 둔다면 이전에 몇 개의 계단을 연속해서 올라왔는지 확인할 수 없다. 그래서 2차원배열을 이용해 result[k][1]은 연속해서 1개의 계단만 이용해서 k번째 계단까지 올라왔을때의 최대값을 의미한다. 이 말은 k-1번째 계단을 이용하지 않고 k-2번째 계단을 밟았다는 얘기이다. 그렇기때문에 result[k][1] = max(result[..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 점화식을 못찾아서 힘들었따.. 아직은 모르지만 dp문제는 테이블에 들어가는 값이 어떤 의미인지와 점화식만 찾으면 해결할 수 있는듯하다. 아무튼 result[k]의 값은 result[k-1] + result[k-2] + result[k-3]이다. 그러므로 초기값을 최소 세 개가 필요할 것이기때문에 1,2,3의 경우 값을 미리 넣어주었따. 이 문제에서는 여러 케이스에 대해서 결과를 출력하는 것이므로 아예 배열을 바깥에다 선언후에 각 케이스별로 매번 새로 구해주는 것이 아니라 값이 없는 경..