https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 저번에 푼 부분합 문제의 소수 버전. 비슷한 문제여서 금방 해결 가능했다. 아이디어 1. 소수 찾기 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다. 2. 소수의 연속합 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다. 전체 코드 import math n = int(input()) if n == 1: print(0) exit(0) arr = [True] * (n + 1) arr[0] = False arr[1] = False for i in range(2, int(math.sqrt(n)+..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제. 아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 아이디어 1. 그래프 일단 보자마자 그래프를 써야 한다고 생각했다. 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다. 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다. 2. dfs 방문 유무를 통해 사이클이 생겼는지 안 생겼는..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 아이디어 1. 부분합 사용 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다. 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. ..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 아이디어 1. 가중치가 있는 그래프 다익스트라 아니면 플로이드 두 개를 생각했다. 두정점 v1, v2를 지나는 최단경로는 각각의 최단경로들을 더한 것과 같으므로 다익스트라를 여러 번 사용하면 된다. '1 -> N' = '1 -> v1' + 'v1 -> v2' + 'v2 ->N' 같이 계산해서 두 정점을 지나는 최단경로를 구한다. 루트는 1 -> v1 -..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 아이디어 1. 구현이 먼저 문제를 보고 N최대가 20이고 이동도 5번 하므로 문제가 말한 그대로 구현하면 되겠다고 생각. 상, 하, 좌, 우 이동 중에 '좌'로 이동하는 것부터 구현하면 나머지도 쉽게 만들 수 있다. 만들수록 변수나 if문이 많아져 다시 밀고 처음부터 작성했다. 너무 많은 변수는 필요 없다. 이건 다른 구현 문제도 마찬가지라고 생각. '이동시킬 블록'과..
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 1. 백트래킹 이미 N과 M 문제를 풀어봐서 바로 떠올랐다. 깊이가 M이 될 때마다 주어진 숫자들을 탐색하면 된다. 이 문제에서는 순열, 중복되지 않은 숫자들을 나열해야 하므로 이미 추가된 숫자가 있으면 continue로 넘겨준다. 전체 코드 N, M = map(int, input().split()) numbers = [int(x) for x in input().split()] ..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 아이디어 1. 보석을 가방에 어떻게 담을 건가. 단순히 이중 반복문으로 비교하면 시간 초과가 난다. 다시 문제를 읽고 문제에 있는 힌트를 보고 감을 잡았다. 먼저 보석 리스트와 가방 리스트를 오름차순으로 정렬하고 각 가방을 기준으로 보석이 가방에 넣을 수 있는지 확인한다. 가방에 넣을 수 있는 보석 중 가치가 가장 큰 걸 넣어주면 된다...
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 시리즈 마지막 숨바꼭질 1 먼저 풀어보는 게 좋다. 아이디어 1. bfs 큐에 x +1, x - 1, x * 2를 조건에 맞으면 추가해준다. 큐에 위치와 시간 그리고 지나온 길도 같이 넣어준다. 도착하면 도착 시간과 경로를 리턴 후 출력. 전체 코드 from collections import deque N, K = map(int,input().split(..
