정신차려 하프물범 정신차려 하프물범

문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 풀이 설명 분류: 누적합 모듈러 합의 개념을 알아야 함. (A + B) % M = ((A % M) + (B % M)) % M 덧셈 뿐 아니라 뺄셈, 곱셈 다 해당됨 구간의 합은 누적합 배열에서의 차와 같다. ex. i~j 까지의 부분합 = sum[j] - sum[i-1] 그러므로, 구간의 합 % M = 0 -> (sum[j] - su..

1. 문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 2. 풀이 분류: 누적합, 투포인터 (10 ≤ N < 10만 )과 S (0 < S ≤ 1억) 이므로 O(n)으로 풀어야지, 이중 반복문으론 아무리 break를 걸어도 시간초과 남. while 문 1개로 돌리기.. 누적합 배열 만들어서도 해봤는데 왜 시간초과 나거나 틀렸다고 하는지 모르겠움🤦‍♀️(아직 풀이중) import sys input = sys.stdin.rea..

1. 문제 링크 https://www.acmicpc.net/problem/1182 2. 풀이 n, s = map(int, input().split()) array = list(map(int, input().split())) cnt = 0 def dfs(idx, sub_sum): global cnt if idx >= n: return sub_sum += array[idx] if sub_sum == s: cnt += 1 dfs(idx + 1, sub_sum) dfs(idx + 1, sub_sum - array[idx]) return dfs(0, 0) print(cnt) 3. 후기 백트래킹 문제 유형은 index의 값을 어떻게 넘기는지에 따라 조합, 순열 등 결과에 영향을 많이 받습니다. 대체로 문제에서 시키..

1. 문제 링크 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 2. 풀이 1) 문제 풀이 각 50만개씩인 명단 2개 in으로 판별(시간 초과, n^2 = 2500억개) -> 이진탐색(풀림, 시간 복잡도 50만 * logN = 50만 * 11 정도) -> set활용(풀림, 제일 간단, O(len(s) + len(t)) = 2 * 50만) 두 집합의 교집합, 합집합, 차집합은 2 * O(n)이 2000만을 넘지 않는다면 set 쓰자. 2) 풀이..

1. 문제 링크 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 2. 풀이 1) 풀이 설명 - 빠른 도착지의 짐 부터 싣는데 최적해라는 것 - 도착지를 기준으로 s-r 까지 가장 많이 실을 수 있는 짐의 양을 재는 것이다. 도착지를 기준으로 오름차순으로 정렬한다. 시작부터 도착지 범위에서 min(남은 트럭 용량(capa), 박스 크기(box)) 을 골라서 가장 작은 값을 넣는 것이다. 이때 박스 크기는 달라지지 않지만, 범위..

1. 문제 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 2. 풀이 1) 풀이 설명 분류: 그리디, 스위핑 스위핑은 정렬 후 다음 데이터만 생각하기 때문에 그리디랑 같이 엮인다. => 이럴 경우 heapq 사용하기 heapq(room 배열)에 끝나는 시간을 담아서, 다음 시작 시간이 heapq에 담긴 0번째(가장 빨리 끝나는 시간)보다 클 경우, 배열에 끝나는 시간을 추가한다. 그렇지 않으면 빼고 추가 2) 풀이 코드 import..

1. 문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 2. 풀이 코드 출력 형태가 리스트가 아니라 string 형식이어서 뭐가 틀린지 찾느라 열받았던 문제^,,, import sys input = sys.stdin.readline tc = int(input()) result = [] for _ in range(tc): cmds = input().rstrip() length = int(input()) stack = input().rstrip()[1:-1].split(',') flag = Tr..

문제 링크 https://www.acmicpc.net/problem/2469 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정 www.acmicpc.net 풀이 처음 아이디어로는 '?'를 제외한 나머지 사다리를 탄 후 결과 값과 비교하려 했지만 -> '?'의 위치도 중요해서 복잡해짐. [풀이 참고함] 핵심: 가로줄이 있으면 두 알파벳이 교환된다. 첫 줄(초기값) ~ 물음표 줄 전까지 사다리 타기 진행 & 맨 밑(결과)~물음표 다음줄까지 진행 (아래서 위로) 그럼 물음표 줄을 가운데에 두고 before, '???'..