Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/1915 문제를 요약하자면, 배열 내에서, 1로 된 가장 큰 정사각형의 크기를 출력해야 합니다. 1) 예제 입출력❄️ 예제에서는 가운데 1로 된 2x2 배열이 가장 큰 정사각형이고, 넓이는 4이므로, 4를 출력합니다. 2. 핵심 논리☢️ dp 테이블을 배열과 같은 크기로 하고, 각 행과 열에 그 (행, 열)을 오른쪽 아래 모서리로 하는 최대 정사각형의 한 변 길이를 저장하도록 하는 게 핵심입니다. 3. 풀이 코드✅ 1) 코드 n,m = map(int,input().split()) arr = [list(input()) for _ in range(n)] dp = [[0]*m for _ in range(n)] resu..
C,N = map(int,input().split()) cost_list = [list(map(int,input().split())) for _ in range(N)] dp = [1e7 for _ in range(C+100)] dp[0]=0 for cost, num_people in cost_list: for i in range(num_people,C+100): dp[i] = min(dp[i-num_people]+cost,dp[i]) print(min(dp[C:])) Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/1106 문제를 요약하자면, 얻어야 하는 고객 명수 C와 도시 개수 N이 주어질 때, 다음 N개의 줄에는 각 도시에서 홍보할 때 드는 비용과 그 비..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/9625 문제를 요약하자면, 화면에 A가 표시되어 있고, 버튼이 하나만 있는 기계가 있습니다. 버튼을 누르면 A는 B로 변하고, B는 BA로 변하게 됩니다. K 번 버튼을 눌렀을 때, A와 B의 개수를 구해야 합니다. 1) 예제 입출력❄️ 버튼을 한 번 누르면, 화면에 표시되었던 A가 B로 바뀌고, 출력은 A가 0개, B가 1개로 0 1이 됩니다. 2. 핵심 논리☢️ 한 번 누르면 A:0 B:1입니다. 그다음은 A:1 B:1 -> A:1 B:2 -> A:2 B:3입니다. A와 B가 피보나치의 규칙을 따르는 것을 찾는게 핵심입니다. 3. 풀이 코드✅ 1) 코드 K=int(input()) a,b=0,1 for i i..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/1309 문제를 요약하자면, 우리의 크기 N이 주어질 때, 우리의 크기에 따라 사자를 배치하는 모든 경우의 수를 9901로 나눈 나머지를 출력합니다. 사자는 가로, 세로로 붙어있게 배치할 수 없고, 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 포함합니다. 1) 예제 입출력❄️ 입력으로 4가 주어지면, 4행, 2열짜리 우리에 사자를 채우는 경우의 수를 출력하면 됩니다. 2. 핵심 논리☢️ 길이가 3인 리스트를 원소로 갖는 dp를 만들어서 왼쪽배치로 시작하는 경우, 오른쪽 배치로 시작하는 경우, 배치하지 않는 것으로 시작하는 경우에 대해, dp 테이블을 채워서 마지막 원소를 모두 더해서 출력합니다. 3..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/17404 문제를 요약하자면, 첫째줄에 집 개수 N이 주어집니다. 다음 줄부터는, 집을 R, G, B로 칠할 때 드는 비용이 주어집니다. 집은 빨강, 초록, 파랑 중 하나로만 칠해야 하며 아래 3가지 규칙을 만족하는 최소 비용을 출력해야합니다. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 1) 예제 입출력❄️ 첫 번째 예제를 보면 40 -> 57 -> 13 이렇게 선택했을 때, 최소비용 110이 나오는 것을 볼 수 있습니다. 2. 핵심 논리☢️ 이 풀..
