potato's devlog

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 IDEA 이렇게 발견한 점화식은 아래와 같다. 여기서 dp 는 위에 그림으로 나타낸 최대값들을 저장하는 배열이고, arr 는 우리가 입력받은 스티커들의 가격이 명시되어있는 배열이다. dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i]) dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0..

문제 링크 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 내가 푼 풀이 - 맞았습니다! let n = Int(readLine()!)! var dp = Array(repeating: Array(repeating: 0, count: 10), count: 1001) //sum 함수 구현 func sum(_ numbers: [Int]) -> Int { return numbers.reduce(0, +) } // 한자..

문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 IDEA 사자가 어디 위치에 오느냐에 따라 새로 들어오는 사자들의 위치가 달라진다. 하지만 이 이전에 단순한 숫자규칙이 있는지 찾아보았다. 예시가 N = 4 일때가 주어졌으니, N=1,2,3 을 찾아보았다. N=1 일때 3, N=2 일때 7, N=3일때 17이 되었고, N=4일때는 41이 된다고 했다. 이 숫자들을 통해 규칙을 찾아보면, n-1번째 숫자에 2를 곱하고, n-2번째 숫자를 더해주면 n일때의 값이 나온다는 단순한 숫자규칙이 존재한다. 이처럼 dp 문제에서는 규칙을 찾는 것이 매우 중요하다. 소스코드 -..

문제링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 IDEA 우선, 문제를 읽어보면 조건이 세개 나 달려있지만, 다 같은 말이다. 그저 집의 색상은 앞뒤 집과 겹치지 않아야 한다는 하나의 조건일 뿐인 것이다. 1번집이 빨간색이면, 2번집은 파랑이나 초록이면 되고, 50번째 집이 빨강이라면, 49번집과 51번집은 빨강이 아니면 된다. 나는 이문제를 보고 바로 이 문제(click!!)를 풀었던 경험을 생각했다. 마지..

문제 링크 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 idea 아니 풀다보니, 1,2,3 더하기 관련한 시리즈 문제를 몇개 풀어봤으므로, 더 복잡해야되는데 이게 규칙이라고? 하면서 애매모호하게 풀었던 문제였다. 근데 아니나 다를까 1,2,3더하기 (백준 9095번) 문제랑 그냥 동일한 문제였다. ㅋㅋㅋㅋ 괜히 쫄았네... https://didu-story.tistory.com/225 [백준] (Swift) 9095번 - 1,2,3 더하기 (스위프트 다이나믹 프로그래밍 풀이) 문제 링크..

문제 링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA 규칙을 찾다가 2차원배열로 풀어야한다는 생각을 미처 하지 못해서 인터넷을 참고했다. dp 도 다양한 유형을 풀며 어떤 상황일 경우 어떻게 접근해야하는지 감을 익혀야하는 것 같다. 규칙찾기가 힘들었다. 이런 문제가 나오면 2차원으로 풀자. k개를 더해서 n을 만드는 경우의 수를 배열로 넣으면 된다. 2차원 배열일 경우 표를 그리면서 규칙을 찾아나서면 된다. 생각보다 간단한 규칙이 있다. dp는 무조건 규칙부터! 규칙을 설명해보겠다. 우선 위에서 적은것 처럼 k개의 수를 더해서 n을 만들자! 라는 맥락..

문제링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 풀이 IDEA 우선 dp 문제를 만나면, 규칙을 파악하기 쉽게 모든 경우의 수를 수기로 써본다. 이렇게 작성해보았다. 문제의 규칙이 보일듯, 보이지 않았다. dp 배열에 1일때 항의 수 1, 2일때 항의 수 2, 3일때 항의 수 3, 4일때 항의 수 1.. 이렇게 넣으려고 하는 건 알겠다. 근데 이제 어떻게 점화식을 만들어야할까? 우선 나는 아..

문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 idea 앞에서 풀던 dp 문제와 다를 것 없는 문제! 앞에서부터 더해주고 max값으로 바꿔주면 돼. 왜냐면!! 어차피 가장 큰 값을 찾는거라 계쏙 max 값으로 업데이트 되기 때문이다. 소스코드 let n = Int(String(readLine()!))! let arr = readLine()!.split(separator: " ").map{Int(String($0))!} var dp ..

문제 링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 IDEA 우선 해당 문제는 LIS를 구현한 이후에, LIS 부분 수열을 출력하는 문제이기 떄문에 아래 두 개의 포스팅을 모두 이해해야 해당 문제를 수월하게 풀 수 있다. ▷ LIS 란? https://didu-story.tistory.com/236 [알고리즘] (Swift) 최강 증가 부분 수열..

문제 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 IDEA 초반에 도대체 이게 무슨 소리야, 그냥 오름차순이면 수열이 되는거임? 라고 생각하며 의아했지만, 바로 그게 잘 이해한 거였다. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequences) 라는 개념인데, 주어진 배열에서 오름차순으로 이루어진 수열 중, 가장 긴..