문제 https://www.acmicpc.net/problem/1890 Algorithm1. 처음엔 재귀함수를 사용해서 백트래킹으로 완전탐색을 시도했는데 시간 초과가 발생했다.2. DP를 사용하여 각 타일에 올 수 있는 경우의 수만 체크하여 각 타일에 갈때마다 dp 이중 배열의 값을 더해줬다. Codeimport java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;public class Main { private static Buff..
Koala - 17기
https://www.acmicpc.net/problem/1965알고리즘 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자에 넣을 수 있고, 한 번에 넣을 수 잇는 최대의 상자 개수를 찾는 코드를 구성해야 하므로, 해당 수열에서 가장 길이가 긴 증가하는 수열을 찾으면 된다. dp배열을 만들고, i번째 원소보다 앞에 있는 원소(0 ~ i-1)들중에 i번째 원소보다 작은 원소의 개수를 카운팅해주어 dp배열에 저장하는 방식으로 구성하였다.https://www.acmicpc.net/problem/11053해당 문제와 코드가 유사하다.코드import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int,inp..
문제요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레드카드오렌지카드퍼플카드블루카드청록카드그린카드그레이카드카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드..
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/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..
