문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용해 풀었습니다. ※ heap에서 꺼낸 비용보다 cost의 비용이 더 작다면 넘어갑니다. (time limit 방지) 코드 파이썬 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = sys.maxsize V, E = map(int, in..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 [수정 전] 브루트포스 알고리즘을 사용해 풀었습니다. tetrominos에 모든 테트로미노에 대해 왼쪽 위 인덱스(x, y)를 기준으로 더할 값을 저장합니다. 모든 테트로미노를 모든 위치에 대조해보며 더 높은 값을 계속해서 업데이트합니다. [수정 후] 백트래킹을 사용해 풀었습니다. 오른쪽, 왼쪽, 아래로 뻗어가면서 테트로미노(4)가 완성되면 더 높은 값을 비교해 업데이트합니다. L이 1..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹을 사용해 풀었습니다. home에 집 위치를, chicken에 치킨집 위치를 저장합니다. DFS를 사용해 M개의 치킨집을 선택해 도시의 치킨 거리를 구합니다. ※ 치킨집은 많을수록 최소 거리에 유리합니다. 코드 파이썬 import sys input = sys.stdin.readline INF = sys.maxsize N, M = map(int, input()..

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 누적합을 사용해 풀었습니다. ramainder에 누적합의 나머지 개수를 저장합니다. \(_{i}{C}_{2}\) 를 계산해 answer에 더합니다. 코드 파이썬 import sys input = sys.stdin.readline N, M = map(int, input().split()) A = list(map(int, input().spl..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 투 포인터를 사용해 풀었습니다. left, right을 0으로 초기화합니다. right가 0부터 N까지 아래 작업을 반복합니다. 누적합(total)이 S 미만이면 누적합에 nums[right]를 더합니다. 누적합이 S 이상이면 미만이 될 때까지 아래 작업을 반복합니다. 최소 길이를 저장합니다. 누적합에서 num[left]를 뺍니다. left를 1 증가시킵니다. right를..

보호되어 있는 글입니다.