Heecheol's blog

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 수를 이어붙이는 문제여서 처음에는 앞자리와 연관을 지어서 생각했었다. result[k][1]은 n이 k일때 맨 앞자리가 1인 경우라고 생각하며 풀어보았지만 해결할 수 없어서 뒷자리를 이용해보기로했다. 그래서 result[k][i]는 n이 k일때 마지막 자리가 i인 경우로 생각했다. 이렇게 생각하니 마지막 자리수가 정해지면 나머지는 길이가 n - 1일때의 경우가 되는 것을 알 수 있었다. 따라서 식은 아래와 같이 구할 수 있었다. result[k][i] = result[k - 1][i - 1] + re..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 처음에는 result라는 1차원배열을 따로 두어 result[k]가 k층까지 더한 값의 최대값으로 설정하려고했다. 만약 k층까지는 최대값이지만 다음층에서 더할 수 있는 숫자가 매우 작다면 k + 1층에서는 result[k]값이 쓸모가 없게된다. 그래서 이렇게 하지 않고 반복문을 통해 triangle변수의 각 자리를 누적된 합으로 정해주기로 하였다. 예시를 들어보면, 1층에 7이 있고 2층에 3과 8이 있다고 하자. 그러면 1층에는 7이 그대로 있고, 2층의 ..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 전형적인 dp문제였던 것 같다. 다른 사람들의 풀이를 보면 내가 좀 복잡하게 푼 것 같긴하다. 우선 maxValue라는 변수를 이용해 원래 배열의 최대값을 구해준다. 그리고 cache라는 변수를 이용해 이름뜻대로 지금까지의 값을 담아주도록 하였다. 이때, 새로운 수인 numbers[i]와 더했을 때 0보다 작아지지않으면 계속해서 더해주도록 했다. 계속해서 result 변수에 지금까지의 cache와..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 이전에 풀었던 문제와 비슷하게 접근했다. 각 경우마다 앞에 1이 있을 때 뒤에 어떤 것이 올 수 있는지, 00이 있을 때 뒤에 어떤 것이 올 수 있는지를 구해보니 운이 좋게 바로 식을 구할 수 있었다. 앞에 1을 붙이면 뒤에 붙을 수 있는 숫자의 개수는 n - 1개이다. 그래서 result[n - 1]의 값을 확인해봤더니 맞았다. 또한 앞에 00을 붙이면 뒤에 n - 2개의 숫자가 붙을 수 ..

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