9. 20159 동작 그만. 밑장 빼기냐? 9.1. 문제유형 누적합 9.2. 풀이과정 밑장 빼기는 나, 상대방에게 주는 경우와 하지 않는 경우가 있다. 내 차례에 밑장을 빼는 경우, 상대방 차례에 밑장을 빼는 경우를 고려한다. 예를 들어 1,2,3,4,5,6,7,8,9,10을 대상으로 계산 후 점화식을 도출해 볼 수 있다. 점화식을 도출할 때, 미리 짝수/홀수 인덱스에 대한 누적합을 계산한 후 점화식에 활용한다. 9.3. 소스코드 n = int(input()) card = list(map(int, input().split())) mid = n//2 odd, even = card[0::2], card[1::2] answer = sum(odd) for i in range(1, mid): odd[i] += o..

7. 14465 소가 길을 건너간 이유 5 7.1. 문제유형 누적합, 슬라이딩 윈도우 7.2. 풀이과정 정상 신호등의 누적합 개수를 구한다. k개의 연속된 신호등을 구할 것이므로 i ~ i+k-1까지의 값을 계산한다. 2번 결과의 최대값을 구한다. k - 최대값 출력 7.3. 소스코드 from copy import deepcopy n,k,b = map(int, input().split()) sign=[1]*(n+1) psum=[0]*(n+1) sign[0]=0 for _ in range(b): broken = int(input()) sign[broken]=0 psum = deepcopy(sign) for i in range(1, n+1): psum[i] += psum[i-1] answer=0 for i ..

5. 21758 꿀 따기 5.1. 문제유형 누적합 5.2. 풀이과정 누적합을 구한 후 꿀통의 위치를 기준으로 3가지 경우에 대해 각 10만번 연산을 수행하였다. 첫 번째는 꿀통이 오른쪽에 있는 경우 벌 한 마리는 가장 왼쪽에 위치 두 번째는 꿀통이 왼쪽에 있는 경우 벌 한마리는 가장 오른쪽에 위치 세 번째는 꿀통이 중간에 있는 경우 이 경우는 양 끝에 벌들이 위치한다. 누적합만 계산해 놓으면 2,3,4를 loop를 돌며 계산할 수 있으므로 O(N)에 해결할 수 있다. 5.3. 소스코드 from copy import deepcopy n=int(input()) h=list(map(int, input().split())) s = deepcopy(h) answer=0 for i in range(1, n): s[..

3. 11660 구간 합 구하기 5 3.1. 문제유형 누적합 3.2. 풀이과정 매 번 2중 for문을 계산할 시 시간초과가 발생할 것이다. 따라서 미리 누적합을 계산해 놓고, 구간별로 뽑아 리턴한다. 이 때, col 인덱스번호가 0이라면 종료값의 누적합을 덧셈한다. 시작 인덱스가 0이 아니라면 종료값 - 시작값을 덧셈한다. python 시간 초과 발생 -> pypy3로 통과 3.3. 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) nums = [list(map(int, input().split())) for _ in range(n)] for i in range(n): for j in range(1, n): nums[i..

1. 20438 출석체크 1.1. 문제유형 누적합 원소별 합계를 구한 후 S[i] - S[i-1]을 활용해 문제를 풀어나간다. 1.2. 해결과정 전체 학생 수만큼 배열을 선언한다. 조는 학생을 체크한다. 출석 번호를 체크한다. 0번째부터 n+3까지 출석한 학생들의 누적합을 구한다. 구간 학생 수 - (누적합[구간 마지막값] - 누적합[구간 시작값]) 1.3. 소스코드 import sys input = sys.stdin.readline n,k,q,m = map(int, input().split()) sleep = [0]*(n+3) check = [0]*(n+3) for i in map(int, input().split()): sleep[i] = 1 for i in map(int, input().split(..

9. 1105 팔 9.1. 유형파악 그리디 그리디 유형은 정렬과 함께 출제될 확률이 높다. 문제 유형을 한 번에 파악하기 어려울 경우 그리디를 의심해볼 것 종종 DP, Graph 알고리즘과 함께 출제된다. 그리디는 반드시 최적의 해를 구할 수 있는 지 의심해봐야한다. 9.2. 해결과정 주어진 l, r 사이에서 8을 가장 적게 포함하는 횟수를 구하는 문제이다. 수의 범위가 20억이므로, 순차탐색으로 해결할 수 없다. 8의 최소 개수만 세면 된다는 것에 초점을 맞춰 풀어야한다. l과 r의 첫번째 자리수부터 비교하되 일치하면서 8이라면 개수를 카운트하고, 다르다면 stop한다. 만약 자리수의 값이 다르다면, (8이 아닌 다른값으로 설정해버리면 개수가 0이된다.) 바로 stop하는 이유는, 이미 앞 자리수가 다..

5. 17609 회문 5.1. 유형파악 Greedy 그리디 유형은 정렬과 세트로 출제된다 바로 문제 유형을 파악하기 어렵다면 그리디를 의심해볼 것 그래도 파악이 어렵다면 DP, Graph 알고리즘을 고려할 것 📌 그리디로 해법을 찾을 때는 항상 정당한 해법인지 의심해봐야 한다. 5.2. 해결과정 문자를 최대 하나 삭제할 수 있으므로 그리디 유형임을 파악. 단, 모든 문자열을 검토할 경우 시간초과 발생. 따라서 유사 회문은 투 포인터 방식으로 구현. 투 포인터로 양 끝에서 같은지 탐색 후, 다를 경우 check_pseudo() 호출. check_pseudo는 왼쪽 삭제, 오른쪽 삭제 2번 호출 왼쪽, 오른쪽 호출된 값 중 하나라도 True라면 1. 아니라면 2 반환 5.3. 소스코드 # val == val..

3. 1946 신입사원 3.1. 문제유형 그리디, 정렬 3.2. 해결과정 그리디 문제지만 지원자가 10만명이므로 2중 for문으로 접근 시 10^10 연산 횟수가 필요하다. 따라서 O(n^2)이하의 복잡도로 문제를 해결해야 한다. 힌트는 서류나 면접점수 둘 중 하나로 정렬하면, 1명은 무조건 합격이라는 것을 알 수 있다. 이를 활용하여 서류로 정렬 후 합격자보다 면접점수가 높은 지원자를 카운트한다. 이전 합격자보다 면접점수가 높은 지원자가 나오면 면접 점수를 갱신한다. 3.3. 소스코드 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): n = int(input()) apply = [list(map(int,input().sp..

1. 1931 회의실 배정 1.1. 문제유형 그리디 1.2. 해결과정 해당 문제는 (종료시간, 시작시간)을 기준으로 정렬한 후 카운트해야한다. 회의를 가장 많이하려면, 빨리 끝나는 회의 먼저 시작한다. 끝나는 시간이 동일하다면, 시작 시간이 빠른 회의를 먼저 시작한다. 현재 종료된 회의시간

10. 1244 스위치 켜고 끄기 10.1. 문제유형 시뮬레이션 10.2. 해결과정 여성일 경우와 남성일 경우를 처리하는 함수를 2개 구성했다. 남성의 경우 받은 번호의 배수에 해당하는 스위치를 Turnoff한다. 배수임을 확인할 때는 입력받은 값을 그대로 사용하되, 인덱싱할 때는 -1 처리한다. 여성의 경우 받은 번호의 양 옆 대칭인 스위치를 Turnoff한다. 입력받은 값을 -1 처리 후 왼쪽, 오른쪽 값을 인덱싱한다. 10.3. 소스코드 n=int(input()) switch=list(map(int,input().split())) s=int(input()) students=[list(map(int, input().split())) for _ in range(s)] def male(num): for ..