링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 소요시간: 38분 10초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 조합으로 풀면 되는 문제다 먼저 빈공간의 리스트를 뽑아낸다 그 후 그 빈공간 중 3개를 뽑는 조합 연산을 수행한다 각 bfs 시도마다 새로운 빈공간 3개씩을 집어넣어서 시뮬레이션을 돌린다 그 후 안전한 공간의 개수를 safe_zone 리스트에 넣는다 3. 출력하기 safe_zone에서의 max값을 출력한다..
링크 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 소요시간: 27분 설계하기(접근방법) 1. 입력받기 카드 팩 리스트를 입력받는다 2. 구현하기 이전에 풀었던 DP 문제와 유사하다 중복되는 조합이 있으면 가장 작은 케이스부터 dp를 처리하고 가장 큰 숫자를 마지막으로 dp를 처리하여 카드 수를 뽑을 때 최대값을 구한다 3. 출력하기 최대값을 출력한다 코드(출력) n = int(input()) pack = list(map(int, input..
링크 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 소요시간: 55분 48초 설계하기(접근방법) 1. 입력받기 팀원 배열을 입력받는다 2. 구현하기 가능한 팀원의 조합을 구해서 배열에 해당되는 값을 더한다 조합의 경우 모든 것을 구할 필요가 없다 앞이 1로 시작하는 케이스 즉 팀원이 2명이라면 1,2 1,3 1,4 만 구해도 3,4 2,4 2,3 이 따라온다 둘 중 한개의 배열에는 1이란 선수가 들어가야 한다 그리고 두 개의 배열은 숫자가 같다 따라서 1..
링크 : https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 소요시간:15 분 설계하기(접근방법) 1. 입력받기 숫자를 입력받는다 2. 구현하기 딕셔너리를 선언해서 나온 숫자의 개수를 더해준다 이 문제는 6과 9를 어떻게 처리하느냐가 관건이다 6, 9 의 개수의 합이 짝수라면 2를 나누어 몫을 저장하고 6,9의 개수가 홀수라면 1을 더해서 2를 나누어 목을 저장한다 3. 출력하기 딕셔너리의 최대값을 출력한다 코드(출력) a = list(map(int, list(input()))) num_dict = {} for i in range(10): ..
링크 : https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 소요시간: 55분 설계하기(접근방법) 1. 입력받기 등수를 입력받는다 2. 구현하기 먼저 현재 등수에 자리 배치가 가능한 사람은 모두 배치한다 그 후 작은 등수를 순서대로 앞에서부터 빈자리를 가득 채운다 3. 출력하기 빈자리에 강제로 앉은 사람의 불만도의 합을 출력한다 코드(출력) import heapq n = int(input()) maybe_rank = [] real_rank = [0 ..
링크 : https://www.acmicpc.net/problem/1459 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 문제 소요시간: 38분 21초 설계하기(접근방법) 1. 입력받기 목표 좌표, 이동 가중치를 입력받는다 2. 구현하기 처음에 while문으로 돌려서 시간초과가 났다 사실 좌표값 만큼 빼는 것이기 때문에 굳이 while문을 안돌리고 몫만 구해서 빼도 되는 것이었다 먼저 x,y 중 하나가 0이 될때까지 만들고, 둘 다 짝수로 만든다 -> 그래서 평행선에서 대각선 이동으로 목적지에 도달할 수 ..
링크 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 소요시간: 31분 25초 설계하기(접근방법) 1. 입력받기 무게와 가치를 입력받는다 2. 구현하기 이 문제는 최대 무게까지 각 무게별로 어떻게 넣어야 최대의 가치가 되는지 구하면 된다 즉 검사를 할 때 dp[i + w] < dp[i] + v 일때 dp[현재 무게 + 넣을 물건의 무게]의 값어치가 dp[현재 무게] 의 ..
링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 소요시간: 1시간 실패 설계하기(접근방법) 1. 입력받기 문자를 입력받는다 2. 구현하기 이 문제는 이중배열을 만들어서 두 문자를 비교한다 A와 CAPCAK 011111 AC와 CAPCAK 011222 ACA와 CAPCAK 011233 .... 이런 방식으로 이전 배열에서 새로운 같은 글자가 나타난 경우 +1을 해준다 이러한 방식으로 가장..
