potato's devlog

문제링크 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 문제 풀이 (첫번째 시도) 한자리수, 두자리수, 세자리수 로 나누어서 아래와 같이 풀이방법을 생각했다. (두번째 시도) - 맞았습니다! 위와 같은 방식으로 생각하니 9, 99, 120 이걸 설정할 방법을 못찾았다. 입력 가능한 숫자가 8자리..? 인데 이걸 다 if문으로 작성할 수도 없는 노릇이고, 그래서 비슷하지만 다른 방식으로 생각해보았다. 한 자리 수, 두 자리 수,,,, 가 아니라 일의 자리, 십의 자리, 백의 자리 이렇게!! 이렇게 하게 되면, 자리의 수가 변하는 거기 때문에 * 10 을 이용해서 설..

문제링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 좌우/상하 로 인접한 사탕을 바꿀 수 있다. 표[1]과 같이 사탕이 주어졌다. 여기서 [0][0] 사탕과 [0][1] 사탕을 바꾸어보자. 표[2] 와 같은 결과가 나온다. 이렇게 되면 행끼리 인접한 사탕의 최고 개수는 2, 열끼리 인접한 사탕의 개수는 3이 된다. 다시 표[1]로 돌아가서 표[1]에서 [0][0] 사탕과 [1][0] 사탕을 바꾸어보자. 표3을 보면, 행끼리 인접한 사탕 최고 개수는 2개, 열끼리 인접한 사탕 최고 개수는 1개 이다. 이 위의 과정을 for 문을 통해서 반복해주었다. 그..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 나의 풀이 먼저 규칙을 찾는데 시간이 조금 걸렷다. 과연 이렇게 푸는게 앞에꺼가 세개 반복되지 않고 구하는게 맞나? 싶었던 의심이 들었었다. 하지만 점화식을 생성하면서, 두번 연속 나온건 제외하고 점화식을 세워주면 되는 거였다. (이게무슨말이지,, 말로표현이 안되네 ㅠㅠ) 어쨋든 풀이는 아래와 같다. 예시로 준것 처럼, 포도주가 6개 주어졌따면, 위와 같이 구할 수 있다. 최대가 될 수 ..

문제 링크 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.. 이렇게 넣으려고 하는 건 알겠다. 근데 이제 어떻게 점화식을 만들어야할까? 우선 나는 아..