![]()
17179번: 케이크 자르기 (acmicpc.net) 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 소스코드 코드설명 N,M,L과 M개의 자를 수 있는 지점을 나타내는 정수 리스트 pnt, N명의 예상 친구 수를 나타내는 정수 리스트 frd 입력 frd 내의 자르는 횟수마다 반복 자를 수 있는 케이크의 길이를 기준으로 설정해 start는 1, end는 가장 긴 L, 답을 저장할 ans는 0으로 설정 mid는 start와 end 중간값, count는 fun(mid)..
https://www.acmicpc.net/problem/2343 문제 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의..
문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 package Koala_study.week_4; import java.util.Scanner; public class s_11053 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 구간합 알고리즘 크기가 N인 배열에 부분합을 구하는 연산을 M번 수행해야 한다고 하자. li[l] + li[l+1] + li[l+2] + ・・・ + li[r]는 다음과 같은 코드를 통해 구할 수 있다. ans = 0 for i in range(l,r): ans += li[i] l, r의 범위가 최악의 경우 0 ~ N-1이므로, 연산의 시간 복잡도는 O(N)이다. 이 연산을 M번 수행해야 하므로 최종적인 시간..
정답 코드 # 치즈 # 복습 횟수:0, 01:00:00, 복습필요O import sys from collections import deque si = sys.stdin.readline N, M = map(int, si().split()) graph = [list(map(int, si().split())) for _ in range(N)] answer = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(): visited = [[0 for _ in range(M)] for __ in range(N)] q = deque() q.append([0, 0]) visited[0][0] = -1 # 방문 처리 while q: x, y = q.popleft() if graph[x]..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net Algorithm sum함수를 사용하면 시간이 초과되므로 투포인터 알고리즘으로 처리하되 부분합을 구할 때 누적합에서 누적합을 빼는 방식으로 진행한다. 부분합이 M 이상이 될 때 그 길이의 최솟값을 구한다. Code import sys input = sys.stdin.readline N, M = map(int, input().split()) array = list(map(int,..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 첫 번째 시도 1개만 제외하고 회문이 되는 경우를 유사 회문이라고 정의할 때, 그 문제가 되는 문자를 찾아서 저장해두고 투포인터로 문자열을 순회하면서 문제가 발생했을 때 사전에 저장한 문제의 문자와 비교하면 되겠다고 가정한 채 구성한 로직이었다. 결과는 실패였다. 가정은 그럴싸하였다고 생각했으나, 문제가 되는 문자를 찾는 로직에 오류가 있어서 제대로 문자를 찾아내지 못헀고, 이는 결국 실패로 이어졌다. import sys fr..
![]()
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net Two Pointer 문제였다 고유 번호들을 정렬하여 리스트에 저장한다 left 와 right를 두고 그 다음 left와 right의 합이 m 보다 작으면 left를 증가 m보다 크다면 right을 감소 해주면서 줄여나간다 합이 m이상이 나오면 count를 +1 해주고 left와 right를 +1, -1 해준다. import sys input = sys.stdin.read..
1.문제 https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 2.해결방법 - 누적합으로 시도해보았으나 .. 실패하고 알고리즘 분류를 보니 슬라이딩 윈도우! 방식이 있어서 슬라이드 윈도우를 통해 구현하였다. - 신호등 (traffic)을 0으로 표시하고 고장난 신호등을 추후에 1로 표시해준다. - 슬라이딩 윈도우를 통해 k개의 신호등이 존재하도록 신호등을 수리할 때 필요한 최소한의 수리 작업을 계산한다. - k사이즈안에서 고장난 신호등(0)을 찾는다. - 윈도우를 이동시키며 맨 앞or 맨 뒤에 있던 신호..
![]()
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 분석 난이도 골드5 분류 이분탐색 들어가기 전에 회문이라는 이름이 들어가는 문제들은 정말 태그가 다양하다. 문제 문제 풀이 풀이 좌우 투 포인터인데 같은 문자가 아니라면 왼쪽 한칸 이동 / 오른쪽 한칸 이동 시켜준 뒤 회문판별을 시켜주면 된다. 소스코드 from sys import stdin input=stdin.readline for _ in range(int(input())): s=input().rstrip() l=0..
문제링크 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) graph = [list(map(int,input().split())) for _ in range(n)] cloud = [[n-1,0],[n-1,1],[n-2,0],[n-2,1]] #초기 구름의 위치 direction = [(0,0),(0,-1),(-1,..
![]()
문제가 없는 신호등은 0, 고장난 신호등은 1로 기록하며 배열을 만든다. k 개의 연속된 신호등의 숫자의 합을 구해보면 그 결과값이 수리해야 하는 신호등의 개수이므로 이 중에서 최소값을 찾아서 출력하면 된다. import sys def main(): n, k, b = map(int, sys.stdin.readline().split()) light = [0]*n for _ in range(b): a = int(sys.stdin.readline()) light[a-1] = 1 start = 0 end = k temp = 0 for i in range(k): temp += light[i] answer = temp while True: if end == n: break temp = temp - light[sta..
