DP3 [Python] 백준 1932번. 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명: 삼각형에서 아래에 있는 수를 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 전에 저장된 값을 활용하고 있다. 7일때 3과 8은 7을 활용하여 최댓값을 구해야한다. 반복적이다. 3은 8을 더하고/ 1을 더해 다음값을 저장한다. 8은 1을 더하고/ 0을 더해 다음값에 저장한다. => 다이나믹 프로그래밍이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 풀이해설: i는 2차원 배열의 길이의 인덱스이.. 2023. 12. 11. [Python] 백준 1149번. RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제설명 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 풀이설계 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최소값을 저장해나가며 모든 집을 칠했을 때 최소값을 구하는 문제이다. DP용 2차원 배열을 하나 더 만들어준다. 첫번.. 2023. 12. 7. [Python] 백준 9184번. 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 설명: 재귀 함수로 실행을 하고 있지만 시간이 너무 걸린다는 문제가 있다. 풀이 방법: dp, 메모이제이션으로 풀어본다. 재귀함수는 일반적으로 연산에 대한 결과를 저장하고 있지 않아 같은 값의 연산도 다시 수행되어야 하는 문제가 있다. 이를 기억하고 있다가 만약 그 숫자들에 대한 연산이 필요하면 값을 꺼내와서 반환하도록 한다. 20보다 크면 무조건 20을 반환하기 때문에 배열은 21을 최대 길이.. 2023. 11. 30. 이전 1 다음