끄적끄적 개발로그

📖 문제 링크 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 👩‍💻 문제풀이 생각보다 규칙이 쉽게 찾아진 문제였다! P(1)부터 P(10)까지 수열을 표로 나열해보니, P(6)부터 규칙적으로 수가 증가하는 것을 확인할 수 있었다. P(6)의 경우, P(1)과 P(5)의 합이며, P(7)의 경우 P(2)와 P(6)의 합인 것을 확인할 수 있다. 즉, 이를 토대로 점화식을 세우면 아래와 같다. dp[i] = dp[i-5] + dp[i-1] dp[1]부..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2 X N 타일 채우기에서 활용했던 방법을 그대로 적용해 보았다. 3X2의 경우 예제에 결과가 나와있으므로, 이를 토대로 3X3을 순차로 구해보았으나 N이 홀수인 경우엔 성립이 불가하다는 것을 발견했다. 그래서 짝수를 기준으로 그림을 그리며 점화식을 세웠다. 문제는, 각 케이스마다 예외가 있다는 것이었다. 3X4의 경우, 3X2의 경우의 수 * 3을 하면 된다고 생각했지만 3X4에서만 나올 수 있는 예외 케이스(빨간 체크)가 있었다. 그래서 dp[4] = dp[2]*3 + 2라는 조건을 성립했다. 여기까지가..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 정말 단순하게도 '제곱수들을 N번째 숫자까지 모두 저장해놓고 큰 수부터 빼면 구해지지 않을까?'라고 생각했다. 하지만 곧 반례를 찾았고, 이미 위와같은 생각에 사로잡혀 다른 방법이 도저히 떠오르지 않았다. 심지어 백준님의 강의로 해설을 듣고 나서도 대체 이것이 어떻게 구현된다는 말인지 아직까지도 이해가 안 되고 있다....... 대충 50% 정도의 현 이해력..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단이라고는 하지만, 이전의 DP문제와 흡사한 방식이다. 조건이 여러 가지이므로 이를 모두 충족시켜야 하는데, 그러지 못해 계속 제출 실패를 했다. 또한 백준에서 제시한 테스트케이스 이외에 다른 케이스를 생각하지 못해 런타임 에러가 발생....^^ 조건은 다음과 같다. 규칙을 찾아보면, dp[i] 는 현재 계단과 전 계단을 밟은 경우의 합이거나, 현재계단과 전 계단을 밟지 않은 경우의 합 중 큰값을 저장해야 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 님의 강의를 참고하였다. 연속된 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제. 이 문제에서 음수를 제하고 푼다는 생각은 하면 안 된다! 음수가 있어도 합이 커질 수 있기 때문이다. (ex. 3, -1, 3) 그리고 연속된 숫자를 고르고 나면, 그 앞에 있는 숫자들은 더의상 의미가 없다.(중요!!!) 이전까지의 DP문제들은 이전의 합에 더해가는 방식으로 식을 세웠다면, 이 문제는 이전..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 증가 부분 수열과 가장 긴 감소 부분 수열을 적용하여, 그 결과를 합하면 해결이 될 것이라 생각했다! 하지만 백준 반례를 도입해서 고민해봐도 도저히 답이 찾아지지 않아 해답을 찾아보았다. 내가 실수했던 것은, 그저 증가수열과 감소수열의 결과에서 각각의 최댓값을 더하면 된다고 생각한 것이었다. 바이토닉 부분 수열이란, 계속 증가되던 부분 수열의 최댓값에서 -> 다시 감소되기 시작하는 수열을 말하는 것! 이해가..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 11053(https://www.acmicpc.net/problem/11053), 11722(https://www.acmicpc.net/problem/11722) 번과 연관된 LIS 문제. 증가 부분 수열 중 합이 가장 큰 것을 구하는 문제이다. 11053번 문제의 코드와 거의 흡사하다. 현재까지의 배열의 합 vs 현재까지 배열의 합 + ..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 11053번(https://www.acmicpc.net/problem/11053) 가장 긴 증가하는 부분 수열의 문제에서 반대로 생각하면 된다. 증가하는 부분수열 문제에서는 현재 인덱스 값(array[i])이 앞의 인덱스(array[j])의 값보다 클 때(array[i] > arary[j]) DP값을 증가시켰다면, 감소하는..

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 문제를 읽고 정말 단순하게 생각했다. 처음 세운 조건은 1차원 배열, 그리고 해당 인덱스(array[i])와 바로 전 인덱스(array[i-1])의 배열 값을 비교하여 큰 값을 dp에 저장하는 방식이었다. 당연히 제출 결과는 실패...^^ 아래의 코드는 위의 조건을 바탕으로 작성한 코드이다. n = int(input()..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 처음 세운 규칙은 1. 현재 잔(w4)+이전 잔(-1)+전전 잔(-3) 2. 현재 잔(w4)+전전 잔(-2)+그이전 잔(-3) 이렇게 두가지 경우로 식을 세워서 풀어보았지만 실패! 그래서 다른 분들의 백준 풀이를 찾아보니, 현재 잔을 마시지 않는 경우를 포함해야한다는 것을 깨달았다. 1. 현재 잔(w4)+이전 잔(w3)+전전 잔(w1) 2. 현재 잔(w4)+전전 잔(w2)+그이전 잔(w1) 3. 현..