https://www.acmicpc.net/problem/14465입력첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.출력정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다. 코드n, k, b = map(int, input().split())arr = [0 for _ in range(n)]for _ in range(b): arr[int(input())-1] = 1 left = 0right = k-1tmp = sum(arr[0:k])ans = tmpwhile right 풀이 과정1. 고쳐야하는 고장난 신호등을 1로 표시2. K 간격만큼에서 고쳐야하는 신호등 수를 그 1들의 합으..
Koala - 17기/코딩테스트 심화 스터디
접근 방법a 배열을 통해 초밥의 가짓수 d(2 ~ 3000)가 k개의 접시를 연속해서 먹을 때 있는지 확인먼저 반복문을 돌려서 0 ~ k-1 접시를 연속으로 먹었을 때 최댓값을 계산(윈도우로 활용)해당 윈도우를 접시를 지우고, 추가하며 연속된 접시를 k 개 먹었을 때, 최댓값을 계산(슬라이딩 윈도우) 코드#include #include using namespace std;int a[3001] = {0, };int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector v(N); for (int i = 0; i > v[i]; int sol = 0, result = 0; for (int i = 0; i
문제 https://www.acmicpc.net/problem/1700 Algorithm그리디 알고리즘cntK_list 에 각 전기용품마다 사용 순서를 따로 deque로 저장한다.그리디하게 해결하기 위해,1. 멀티탭에 플러그가 꽂혀 있고, 해당 전기용품이 꽂혀있는지2. 그렇지않다면 멀티탭에 공간이 남아있는지3. 그렇지 않다면 멀티탭을 정렬한 후, 하나를 뽑는 후 새로 꽂는다. 이 때, 남은 전기용품의 순서를 기준으로 정렬한다. Codefrom collections import dequeinput = __import__('sys').stdin.readlineN, K = map(int, input().rstrip().split())K_list = deque(list(map(int, input().rst..
문제 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..
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 || ..
문제 https://www.acmicpc.net/problem/17142 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..
