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/1300 요약 하자면, 첫줄에 배열의 크기 N이 주어지고 다음줄에 k가 주어집니다. 그러면 NxN 배열 A를 1차원 배열로 만들고 오름차순으로 정렬한 배열을 B라고 할 때, B[k]를 출력해야 합니다. 이 때, NxN 배열 A는 A[i][j] = ixj로 원소들이 있습니다. 예를들어 1행 1열은 1, 1행 2열은 2 이렇게 값이 들어있습니다. 1) 예제 입출력❄️ 2. 핵심 논리☢️ NxN행렬을 1열로 펴지 않고, 각 행에서 trg_value(타겟 값)이하인 수의 개수가 곧 타겟 값의 인덱스임을 이용해서 이분탐색을 하는것이 핵심입니다. 이 때, estimated_idx를 이분 탐색하여 trg_value를 찾기 때..
Contents 1. 문제 정의 및 예제 해석 (문제 링크: https://www.acmicpc.net/problem/14248) 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net 예제를 보겠습니다. 5 : 돌이 5개 있는 경우, 1 4 2 2 1 : 각 돌다리 별로 움직일 수 있는 칸의 개수가 주어집니다. 3 : 출발점이 3번째 있는 돌입니다. 방문 가능한 돌들을 살펴보겠습니다. 1 4 2 2 1 중 빨간 색칠된 곳에서 시작합니다. 처음에 왼쪽으로 2칸 가서 1에 도착한 뒤, 오른쪽..
