11727번 Python 2xn 타일링 문제의 두번째 변형 문제이다. 이번에는 1x2, 2x1, 2x2 타일이 존재한다. 마찬가지로 직접 그림을 그려가보면서 점화식을 구해보는 것을 목표로 한다. 마찬가지로 총 2x4 직사각형까지의 타일을 모두 조합해보았고 다음과 같은 결과를 알 수 있었다. 이번에는 어떤 규칙이 보이는지, 그 규칙이 어떻게 그렇게 되는지 알아보겠다. n의 경우에 n-1 타일을 1번씩 모두 사용했고 n-2 타일은 2번씩 사용한 것을 확인할 수 있다. dp[n] = 2 * dp[n-2] + dp[n-1]따라서 이것이 해당 문제의 점화식이라고 볼 수 있게 되는 것이다. import sysn = int(sys.stdin.readline())dp = [0] * 1001dp[1] = 1dp[2] = 3for i in ran.. 2024. 11. 26. 11726번 Python 이 문제는 어렴풋이 기억나긴 했지만 다시 정리하겠다. 아마 실제로 그려보면 조금 더 빨리 풀 수 있는 것으로 알고 있다. 문제의 의도는 1x2, 2x1 블록으로 2xn의 직사각형을 채울 수 있는 최적의 해를 구하는 문제이다. 실제로 그려보면서 유추되는 식을 찾아보는 것이 메인 포인트이다. 2x1 직사각형의 경우에는 1가지, 2x2의 경우에는 2가지의 형태를 알 수 있다. 2x3의 형태까지만 그려보자. 이렇게 그렸을 경우에도 고려해보자. 무언가 특징이 하나 존재하는데 여기서도 보이지 않는다면 정말 마지막으로 2x4 직사각형까지 그려보자. 개수를 잘 세어보면 피보나치 수열의 형태와 유사한 것을 알 수 있다. 하지만 단순히 시각적으로 보이는 걸 토대로 개수를 세어가는 것보다는 뭔가 더 정확하게 그려지는 형태를.. 2024. 11. 26. 1463번 Python 단순히 문제 해결보다는 문제에서 의도하고자 하는 것이 무엇인지 알아가면서 정리하려고 한다. 어렴풋이 어떻게 풀었는지 기억은 나지만 내가 왜 이렇게 했는지 잊어버렸다. 그렇기에 더욱 더 문제에 대한 정리가 필요한 시점이라고 생각했고 DP의 기초 문제부터 천천히 접근하겠다. 1463번 문제의 경우에는 1로 만들 수 있는 최적의 해를 구하는 것을 목표로 둔다. 10 -> 5 -> 4 -> 2 -> 110 -> 9 -> 3 -> 1문제에도 적혀있는 부분이긴 하지만 10의 경우에는 4번이 아닌 3번만으로도 1을 만들 수 있기에 이것을 어떻게 구현해 나가야 하는지를 생각해보아야겠다. 여기서 dp를 사용하는 것이다. 각 숫자별로 가장 최적의 해를 구할 수 있는 값을 기억해둔다면 그 값을 꺼내 사용하면 될 것이다. 이.. 2024. 11. 26. 2193번 Python 이번에도 점화식을 먼저 찾기 위해 0이 마지막일 때, 1이 마지막일 때를 비교해보았다. d[1][0] = 0d[1][1] = 1d[2][0] = 1d[2][1] = 0d[3][0] = 1d[3][1] = 1마지막 값이 0번째인 거부터 확인해보면 d[3][0] = d[1][0] + d[2][0]이라는 것을 확인할 수 있다. d[i][j] = d[i-2][j] + d[i-1][j]다음과 같은 점화식을 구해낼 수 있다. import sysn = int(sys.stdin.readline())dp = [[0] * 2 for _ in range(n + 1)]cnt = 0for i in range(1, 3): dp[i][0] = cnt cnt += 1cnt -= 1for i in range(1, 3): .. 2024. 8. 22. 11057번 Python 점화식은 스스로 찾아낼 수는 있었는데 코드로써 식을 대입하지는 못했던 것 같다. 0 1 2 3 4 5 6 7 8 91자리의 오르막수는 위와 같이 10개이다. # 0이 마지막인 오르막 수00# 1이 마지막인 오르막 수01 11# 2가 마지막인 오르막 수02 12 222자리의 오르막수는 다음과 같다. 이렇게 해서 2자리는 55개라고 문제에서 나와있는데 사실 55라는 숫자만 봐도 대충 감이 올 사람을 왔을 수도 있다. 1 + 2 + 3 + ... + 9 + 10의 합이 55라는 점을 알고 있으면 점화식을 대강 구해낼 수 있다. 더 효과적으로 구할 수 있게 1~3자리의 마지막이 2인 오르막 수만 구해보자. 2 # 102 12 22 # 1+2002 012 022 112 122 222 # 1+2+3손으로 실제로 .. 2024. 8. 22. 10844번 Python 이 문제는 개인적으로 좀 어려웠는데 이해할 때까지 보면서 대충 감을 잡을 수 있었다. 123, 1234 와 같은 1이 인접한 계단의 수를 구하는 것이다. 이게 왜 DP 알고리즘이 적용되지라고 생각했는데 그 이유를 알 수 있었다. 마지막에 4가 온다고 가정해보자. 4에 인접한 수는 3과 5가 있다. 즉, 34와 54를 일단 둘 수 있고 3에서는 2와 4가 인접하다. 그래서 234 434가 될 수 있다. 이런 식으로 내려가다보면 결국 4자리 수일 때, 마지막에 있는 숫자 4를 기준으로 3으로 끝나는 계단의 수 + 5로 끝내는 계단의 수를 더하면 4자리의 마지막인 계단의 수를 구할 수 있는 것이다. 물론 예외도 있다. 마지막 수가 1이나 9는 인접하는 수가 2와 8밖에 없다. 0으로는 시작할 수 없기 때문이다.. 2024. 8. 21. 이전 1 2 3 4 다음