일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 에라토스테네스의 체
- 3671
- 냅색문제
- 18248
- meet in the middle
- 9328
- 마스크 5부제
- 18235
- 18249
- 메일 전체 읽기
- 그르다 김가놈
- 카드 놓기
- 산업 스파이의 편지
- 마스크 재고 확인
- 공적 마스크
- 알고리즘
- 18113
- 욱제가 풀어야 하는 문제
- 깊이 우선 탐색
- 퇴사 2
- 18114
- image crawling
- 다이나믹 프로그래밍
- 부루트 포스
- BOJ
- 단어 수학
- 15486
- 이분 탐색
- 18115
- 9466
- Today
- Total
목록알고리즘/BOJ 문제 풀이 (14)
groti's blog
1. 문제 해석 https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. (1 ≤ L ≤ 109, L은 정수) www.acmicpc.net N개의 김밥이 있다. 김밥의 양끝은 Kcm 잘라낸다. 김밥의 길이가 2 * Kcm보다 짧을 경우 한쪽만 자고, Kcm 이하면 버린다. 손질된 김밥을 Pcm 크기로 일정하게 자르려고 할 때, M개 이상의 김밥 조각을 얻을 수 있도록 하는 P의 최대값을 구해야 한다. 2. 접근방법 1부터 가장 긴 깁밥의 ..
1. 문제 해석 https://www.acmicpc.net/problem/18114 18114번: 블랙 프라이데이 첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 108, w는 양의 정수) www.acmicpc.net N개의 물건이 있다. 물건의 무게는 모두 다르다. 최대 3개의 물건을 선택하여 무게 C를 맞출 수 있는 조합이 가능한 지 판단해야 하다. 물건의 중복 선택은 불가능하다. (1 M; for (int i = 0; i > arr[i]; chk[arr[i]] = true; }..
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번까지 학생이 있다. 각자 원하는 팀원의 번호를 선택해야 한다. 각 팀원들의 선택이 사이클을 형성하면 팀이 결성..