문제https://www.acmicpc.net/problem/11578문제 설명모든 문제를 풀 수 있는 팀을 만들어야 한다.팀원의 수가 많을수록 상금이 적어지기 때문에 최소한의 팀원으로 우승해야 한다.풀이각각의 팀원들을 묶어가며 해당 팀원들로 모든 문제를 풀 수 있는지 확인하는 문제이다.브루트포스를 통해 하나씩 비교해가며 풀 수 있다. 하지만 각각의 문제를 하나의 비트라고 생각하고 모든 비트가 채워졌을 때 우승할 수 있다고 생각하여 비트마스킹을 이용했다. 각 학생이 풀 수 있는 문제를 비트 처리하여 students 배열에 넣는다.students 배열의 학생들을 조합을 이용하여 해당 조합이 우승이 가능한 지 확인한다.인원이 적은 순으로 확인하기 때문에 가장 먼저나온 조합이 최소한의 팀원이므로 팀원 수를 반..

문제https://www.acmicpc.net/problem/16493문제 설명서로 독립적인 여러 챕터가 존재하며 한 챕터를 읽으면 끝까지 읽어야 한다.$N$일 동안 $M$개의 챕터를 읽어야 한다.$N$일간 읽을 수 있는 최대 페이지 수를 구해라.풀이챕터는 물건, 페이지 수는 무게라고 생각하면 배낭 문제와 똑같다고 생각했다.따라서 DP를 사용하는 배낭 문제 알고리즘을 적용했다. 챕터 중 한개를 선택한다.1부터 최대 페이지 수 까지 비교해 보면서 해당 챕터를 읽었을 때 최대 페이지 수를 갱신한다.마지막 챕터까지 검사를 하면 dp배열의 마지막 인덱스에 최댓값이 갱신된다.코드import sysinput = sys.stdin.readlinetotal_value,total_item = map(int,input()..

문제https://www.acmicpc.net/problem/28215문제 설명KOI 마을에는 N개의 집이 존재하며 N개의 마을 중 K개의 대피소를 뽑는다.각각의 집과 대피소와의 거리를 계산한다나머지 집들 중 대피소와 가장 거리가 먼 집과 대피소와의 거리가 최소가 되도록 대피소를 선택한다.두 좌표 사이의 거리 계산식: $|X_2 - X_1 | + |Y_2 - Y_1 |$ $N=5$일 때 $(1,5)$, $(3,0)$, $(3,3)$, $(6,12)$, $(8,9)$위치에 집이 존재한다고 가정하자.1. 대피소의 위치가 $(3,0)$, $(1,5)$일 때 $(3,0)$$(1,5)$최솟 값$(3,3)$$3$$4$$3$$(6,12)$$15$$12$$12$$(8,9)$$14$$11$$11$각 집에서 대피소와의 거..

문제https://www.acmicpc.net/problem/14646문제 설명욱제는 돌림판을 돌려 걸린 칸에 스티커가 붙어있지 않다면 스티커를 붙인다.돌림판을 돌려 걸린 칸이 이전에 걸렸던 칸이라면(스티커가 붙어있다면) 해당 칸을 제거한다.돌림판을 돌려도 제거된 칸에는 절대로 멈추지 않는다.해당 과정을 반복한다.풀이뽑은 칸 순서를 담은 배열을 순차적으로 탐색한다.해당 칸이 처음 뽑힌 칸이라면 check배열에 방문 처리를 해주고 스티커의 수를 1 증가시킨다.현재 스티커의 최대 값을 갱신한다.현재 뽑은 칸이 이미 check되어 있다면 스티커를 1 감소시킨다.코드import sysinput = sys.stdin.readlinen = int(input())check = [0 for _ in range(n*2)..

문제https://www.acmicpc.net/problem/1816문제 설명어떤 수 S가 주어진다.S의 모든 소인수가 10^6보다 크다면 그 수는 적절한 암호키이다. 그렇지 않은 경우는 적절하지 않은 암호 키이다.적절한 암호키는 "YES", 그렇지 않으면 "NO"를 출력한다.풀이S의 모든 소인수가 $10^6$보다 커야하므로 S를 $10^6$보다 같거나 작은 수로 나누었을 때 0이 나오는 수가 존재한다면, 적절한 암호키가 될 수 없다. S는 최대 10이므로 $10 * 10^6 = 10^7$회로 연산이 가능하다. 해당 문제의 시간제한인 2초($O(10^8)$)에 충분히 여유로운 시간이다. S를 입력받는다.S를 $10^6$보다 같거나 작은 수로 나눈다.1 S % i == 0 이라면 해당 수는 암호키에 적합하..