groti's blog

1. 문제 해석 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 읽고 재귀로 완전탐색하면 되겠다 싶었는데 N 제한이 30 인 것을 보고 고민에 빠졌다. 모든 경우를 확인할 때 최대 2^30번을 확인해야 하기 때문이다. 그래서 알아본 Meet in the Middle 알고리즘을 적용하면 수행시간을 크게 줄일 수 있다. (개념 참고: Meet in the Middle) 최대 C만큼의 무게를 담을 수 있는 가방이 있다. N개의 물건이 있..

1. 문제 해석 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 1~n번까지 학생이 있다. 각자 원하는 팀원의 번호를 선택해야 한다. 각 팀원들의 선택이 사이클을 형성하면 팀이 결성..

1. 문제 해석 https://www.acmicpc.net/problem/9328 9328번: 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 www.acmicpc.net 최대 100*100 크기의 이차원 배열의 주어진 맵에서 획득 가능한 문서($)의 개수를 구하는 문제입니다. 알파벳 대문자(A..

1. 문제 해석 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net N일 동안 최대한 많은 일을 하려고 한다. ( 1 N; for (int i = 0; i > t[i] >> p[i]; } for (int i = N - 1; i >= 0; i--) { int col = i + t[i] - 1; if (col