알고리즘/dp15 [DP] 9184 - 신나는 함수 실행 (실버2) with Python https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 주저리 주저리 문제에서 대놓고 시간이 오래 걸린다고 하고 있다. 재귀를 빠르게 끝내는 방법인 분할 정복 or dp 중에서 고르라는 것 같은데 문제를 보니 피보나치 처럼 이전 값을 메모라이징 하는 것이 옳다 판단해 dp로 작업을 시작하였다. 문제 풀이 일단 w함수를 수도코드에서 파이썬에 맞게 코드를 고쳐주었다. 그렇게 이제 dp를 만들고 메모라이징을 할려는 순간 a,b,c의 범위에 마이너스가 포함된 것.. 2023. 2. 18. [DP] 1149 - RGB 거리 (실버1) with Python https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 주저리 주저리 문제를 읽자마자 이게 어떻게 풀어야 할까 순간 고민을 했다. 하지만 시간이 0.5초이고... 그러면 적어도 브루트 포스나 백트래킹은 아닐거라 판단하였다. 하지만 탐색하면서 찾아야 하는 거기에 그럼 DP를 도입하기로 결정하였다. 문제는 간단하다 이웃하는 집과는 색이 달라야한다 끝! 다행이 첫 집과 끝 집이 연결되어 있는 원형모양이 아닌 직선모양인것이 쉬운 점이라 .. 2023. 2. 18. [DP] 11726 2*n 타일링 (실버3) with Python 너무 오랫동안 코딩에 손을 땐 상태여서 그런지 많이 실력이 줄었다. 그래서 일단 간단한 문제로 시작해 볼까 한다. => 점차 실버 -> 골드로 넘어가볼려고 한다. 목표는 코테를 그것도 네카라쿠배당토 되는 회사들의 코테를 무난하게 합격해 면접까지라도 가는 것이 목표이다. 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. dp의 대표적인 문제인 타일링 문제라고 생각한다. 일단 dp이니 규칙이 있는지를 찾아보자 만약 n = 1 이라면 경우의 수는 세로인 경우 하나일 것이다. 만약 n = 2 이라면? => 세로로 2개를 만들거나 가로로 두개를 만드는 방법으로 2가지가 나온다 n = 3 이라면.. 2023. 2. 18. 이전 1 2 3 4 다음 728x90
