https://www.acmicpc.net/problem/1915입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.출력첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 코드n, m = map(int, input().split())dp = [[0]*m for _ in range(n)]arr = [list(map(int, input())) for _ in range(n)]ans = 0for i in range(0, n): for j in range(0, m): if arr[i][j] == 1: if i == 0 or j == 0: dp[i][j] = 1 els..
분류 전체보기
https://www.acmicpc.net/problem/2618유형다이나믹 프로그래밍문제어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다.모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, ..
https://www.acmicpc.net/problem/14495접근 방법f(1) = f(2) = f(3) = 1 이므로 미리 초기화, n을 입력받아 n번째 피보나치 비스무리한 수를 출력해야 하므로, vector로 선언(배열로 해도 굳이 상관은 없을듯)f(n) = f(n-1) + f(n-3) 이므로, v[i] = v[i-1] + v[i-3] 으로 반복문을 돌며 n번째 비스무리한 수까지 계산 코드#include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; if (n == 1 || n == 2 || ..
4435번: 중간계 전쟁알고리즘:DFS(깊이 우선 탐색)를 활용하여 백트래킹으로 문제를 해결한다. 이를 통해 각 전투의 결과를 저장하고 출력하도록 구현하였다.코드:G_S = [1, 2, 3, 3, 4, 10] S_S = [1, 2, 2, 2, 3, 5, 10] def cbr(g_c, s_c): g_t = sum(g_c[i] * G_S[i] for i in range(len(G_S))) s_t = sum(s_c[i] * S_S[i] for i in range(len(S_S))) # 결과 비교 if g_t > s_t: return "Good triumphs over Evil" elif g_t
문제 https://www.acmicpc.net/problem/23559 Algorithm그리디 알고리즘, 정렬일반적으로 A를 선택하는 것이 더 최선일 것이라 가정하고,예외적으로 B가 최선인 경우, 그리고 금액에 맞도록 선택 횟수를 조정 한 뒤,메뉴를 1. A, B의 차이가 최대 2. A의 맛, 3. B의 맛을 기준으로 내림차순하여 그리디하게 선택한다. Codeinput = __import__('sys').stdin.readlineN,X = map(int, input().rstrip().split())menu_list = [list(map(int, input().rstrip().split())) for i in range(N)]cnt_A, cnt_B = 0, 0ans = 0for i in menu_..
문제문제https://www.acmicpc.net/problem/14888 Algorithm최대, 최소 정답을 미리 설정 후 dfs 함수를 통해 백트래킹을 진행한다.idx가 목표값에 도달하면 결과를 비교후 저장하고 dfs함수가 끝나면 정답을 출력한다. Coden = int(input())number = list(map(int, input().split()))add, sub, mul, div = map(int, input().split())max_result = - int(1e9)min_result = int(1e9)def dfs(add, sub, mul, div, sum, idx): global max_result, min_result if idx == n: max_result..
https://www.acmicpc.net/problem/20950문제 분석분류브루트포스 알고리즘백트래문제 설명미미는 미적 감각이 뛰어난 미술가이다. 미미는 때때로 여러 물감을 섞어 새로운 색의 물감을 만들고는 한다. 어느 날 그림을 그리던 미미는 놀라 자빠질 수밖에 없었다. 미미가 가장 아끼는 곰두리색 물감이 다 떨어졌기 때문이다. 하지만 미미는 새 물감을 살 돈이 없다. 물감은 역시 섞어 써야 제맛이다. 미미는 남은 물감들을 섞어 곰두리색 물감을 만들기로 결심하였다.먼저 RGB 표기법에 대하여 알아보자. RGB 표기법은 빨간색(Red), 초록색(Green), 파란색(Blue)을 혼합하여 색을 나타내는 방법으로, 각각의 색은 밝기에 따라 0부터 255까지의 정수로 표현한다. 예를 들어, 분홍색은 rgb..
문제 https://www.acmicpc.net/problem/14888 Algorithm문제에서 n의 개수는 2~11개, 연산자의 개수는 4개임을 알려줬으므로 각각 11개와 4개의 배열을 생성한다.최대와 최소 역시 -10억 ~ 10억 사이기 때문에 각각 10억 1과 마이너스 10억 1로 설정한다.answer함수에서는 재귀를 통해 더하기부터 차례로 계산한다. Code#include using namespace std;int n;int operands[11];int operators[4];int ans_max = -1000000001;int ans_min = 1000000001;void answer(int result,int idx){ if (idx == n) { if (result > ans_ma..
https://www.acmicpc.net/problem/9291알고리즘스도쿠를 풀때처럼 단순하게 한 열에 대해서 1~9 확인한 행에 대해서 1~9 확인3*3 정사각형에 대해서 1~9 확인일련의 3가지 과정을 거친후 모든조건에 맞다면 스도쿠의 올바른 답인것을 확인 할 수 있다.코드import sysinput = sys.stdin.readlinet = int(input())for case in range(1,t+1): arr = [] for _ in range(9): arr.append(list(map(int,input().split()))) flag = True #check row for i in range(9): checked = [False]*9 ..
문제 https://www.acmicpc.net/problem/9996 Algorithm입력받은 패턴의 *를 제외한 문자들의 길이가 입력받은 문자열 보다 길다면 일치하지 않다. 이를 제외한 경우 패턴과 입력받은 문자열의 시작 인덱스인 0과 패턴의 배열 마지막인덱스 패턴문자열 길이 -1, 입력받은 문자열의 마지막 인덱스인 문자열 길이 -1로 하여 앞쪽부터 하나씩 *를 만나기 전까지 계속해서 입력받은 문자열과 패턴을 상호비교 만약 비교도중 하나라도 다르다면 반복문을 탈출과 일치하지 않음을 반환 만약 앞쪽이 별표전 까지 모두 일치하다면 뒤쪽부터 한칸씩 상호 비교한 이후 뒤쪽도 불일치가 나온다면 반복문 탈출 모두 동일하다면 찾았음을 반환 이후 해당하는 문자열을 출력 Code#include#includeu..
https://www.acmicpc.net/problem/1895입력첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.출력첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다. 코드r, c = map(int, input().split())cnt = 0pixel = []ans = []for i in range(r): pixel.append(list(map(int, input().split())))t = int(input())for x in range(r-2): for y in range(c-2): comp = [pixel[x][y], pixel[x][y+1], ..
https://www.acmicpc.net/problem/2839문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)출력상근이..
