Heecheol's blog

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 1로 만들기 문제와 푸는 법은 동일하지만 경로를 구해야한다. numbers라는 배열을 만들어 각 경우에서 이전 값이 어떤 값이 었는지 추가해주었따. 이렇게 하면 numbers[k]는 k 이전의 값이므로 반복문을 통해 경로를 추적할 수 있다. import Foundation let n = Int(readLine()!)! var result = Array(repeating: 0, count: n + 1) var numbers = [0,1] if n == 1 { print(0) print(1) e..

문제 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[..