Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/1516 문제를 요약하자면, 스타크래프트처럼 건물을 짓는데, 순서관계가 있는 경우, 주어진 N개의 건물에 대해 짓는데 걸리는 최소 시간을 출력해야 하는 문제입니다. 1) 예제 입출력❄️ 첫 줄에 건물 개수(N)이 5로 주어집니다. 다음 5줄 동안 각 건물을 짓는 데 걸리는 시간과, 해당 건물을 짓기 위해 필요한 건물들이 공백을 구분자로 나오고, 마지막엔 항상 -1로 끝납니다. 해당 예시를 보면 1번 건물은 바로 지을 수 있으므로 그대로 10시간을 출력하면 됩니다. 두번째 건물은 1번 건물을 지어야 지을 수 있기 때문에, 1번 건물을 짓는데 걸리는 10시간과 2번 건물을 짓는데 걸리는 10시간을 합해 20시간을 출..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/14939 문제를 요약하자면, 10X10에 켜진 전구는 O로, 꺼진 전구는 X로 주어지는데, 전구의 스위치를 누르면 십자가 모양으로 해당 전구와 위, 아래, 왼쪽, 오른쪽 전구의 상태도 바뀝니다. 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치 개수를 출력해야 합니다. 1) 예제 입출력❄️ 예제를 보면, 맨 왼쪽 위와 맨 오른쪽 아래는 각각 1번씩 가운데 전구의 스위치를 눌러주면, 모두 꺼집니다. 가운데를 보면 가운데 ## 이렇게 되어있는데, 왼쪽 #을 누르면, 오른쪽에 켜진 전구가 십자가 모양이 되어 한번 더 눌러 모두 끌 수 있습니다. 그래서 총 4번 눌러 모든 전구를 끌 수 있습니다. 2. 핵심 논리☢..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/16986 문제를 요약하자면, 3명이서 인싸 가위바위보를 할 때의 우승자를 정하기 위한 구체적인 방식은 아래와 같습니다. (편의상 참가자 3명을 A, B, C) A, B, C는 게임 시작 전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의합니다. 경기 진행 순서가 A, B, C라고 가정하겠습니다. 먼저 A와 B가 경기를 진행해 승자를 결정합니다. 만약 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주합니다. 즉 A와 B가 같은 손동작을 내면 B의 승리, A와 C가 같은 손동작을 내면 C의 승리, B와 C가 같은 손동작을 내면 C의 승리입니다. 이전 경기의 ..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/12100 문제를 요약하자면, 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어집니다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어집니다. 0은 빈칸을 나타내며, 이외의 값은 모두 블록을 나타냅니다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱 꼴입니다. 블록은 적어도 하나 주어집니다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력해야 합니다. 1) 예제 입출력❄️ 상, 하, 좌, 우로 움직일 때 판의 모든 블록들이 함께 움직입니다. 이 때 5번 이동시켜 얻을 수 있는 가장 큰 블록을 출력해야 합니다. 위의 예시에선 5번 어떻게 움직여도 맨 아랫줄 8..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/2961 요약하자면, 재료의 개수 N이 주어지고, 다음 N개의 줄 동안 각 재료가 갖는 신맛과 쓴맛을 입력받습니다. 1개 이상의 재료를 사용했을 때 각 재료의 신맛은 모두 곱해지고, 쓴맛은 모두 더해집니다. 이 때, 신맛과 쓴맛의 차이가 가장 작을 때를 출력하면 됩니다. 1) 예제 입출력❄️ 재료가 1개일 때입니다. 해당 재료만 고르면 되고, 신맛은 3이고 쓴맛은 10입니다. 그 차이는 7이므로, 7을 출력합니다. 2. 핵심 논리☢️ 재료의 신맛, 쓴맛을 이중리스트로 받습니다. 재료에 대해 1개~N개를 선택하는 combination을 모두 고려하여, 각각 신맛 쓴맛의 차이를 result에 min으로 갱신하는 것이..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/1007 문제를 요약하자면, 첫 줄에 테스트 케이스 T가 주어지고, 각 테스트 케이스에 대해 점의 개수 N이 주어집니다. 다음 N개의 줄에 x, y 좌표가 주어집니다. N은 항상 짝수입니다. 좌표 평면에 N개의 점이 있을 때, 모든 점을 사용해서 벡터를 N/2개 만들 때 벡터의 합이 최소가 될 때 최솟값을 출력해야 합니다. 1) 예제 입출력❄️ 첫 번째 예시는 4개의 점에 의해 정사각형이 만들어지기 때문에, 서로 반대방향의 벡터를 가로나 세로로 만들면 합했을 때 최솟값 0이 나오며, 두 번째 예시는 두 점이기 때문에 두 점에 의한 벡터의 길이가 곧 벡터의 합이 되어 길이를 출력하면 됩니다. 2. 핵심 논리☢️ 먼..
Contents 1. 문제🔥 링크: https://www.acmicpc.net/problem/16439 문제를 요약하자면, N명의 회원들에 대해, M개의 치킨에 대해 선호도가 주어졌습니다. 3개의 치킨만 골라서, 각자 3개의 치킨 중에 선호도가 제일 높은 치킨의 선호도를 N명에 대해 만족도의 합이 최대가 되도록 출력해야 합니다. 1) 예제 입출력❄️ 예제 입력 1을 보면, 첫번째, 세 번째, 다섯 번째 치킨을 고른 경우, 첫 번째 회원(1행)의 만족도는 5번째 치킨의 만족도인 5이고, 두 번째 회원(2행)은 첫 번째 치킨의 만족도인 5이고, 세 번째 회원(3행)은 3번째 치킨의 만족도인 3으로 합이 13이 되며, 이게 만족도의 합중에 최댓값입니다. 2. 핵심 논리☢️ 치킨의 종류에 대한 모든 3가지 co..
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. 핵심 논리☢️ 이 풀..
