A. If at first you don't succeed...
총 $n$명 중 A파티장에 간 인원 $a$명과 B파티장에 간 인원 $b$명, 두 파티장 모두 간 $c$명이 주어진다. 그런데 나는 두 파티장 모두 가지않고 집에 있었다. 파티장에 가지않은 인원을 구하는 문제다. $a,b,c,d$이 불가능한 숫자들이면 -1을 출력한다.
$a,b$의 교집합이 $c$명이고 총 표본이 $n$명인데 나는 파티장을 가지않았으므로 $(a \cap b)^c$가 1 이상임이 보장되어야한다. if문 하나로 처리가능하므로 생략.
$n$개의 과목의 점수가 주어지고, 각 과목의 점수는 최대 5점이다. 평균점수가 4.5점만 넘으면 성적표에는 5점으로 기록되는데, 5점으로 기록되기 위해 몇몇과목들을 재수강해야한다. 재수강해야하는 최소과목을 구하는 문제다.
오름차순정렬후 작은 녀석부터 5점으로 만들어주면서 평균점수가 4.5점이 넘는지 체크하면 된다. double형 오차라는 변수가 있기 때문에 평균점수가 4.5일 때가 아닌 총 점수가 4.5 * $n$일때로 계산하자.
사탕상자에 $n$개의 사탕이 들어있다. 나는 매일 $k$개의 사탕을 사장상자에서 먹는데, 손버릇이 나쁜 다른 친구가 내가 먹고 난 뒤 상자의 10%에 해당하는 사탕을 훔쳐간다.(소수점은 버리고 정수개만 훔쳐간다.)그리고 나는 사탕이 $k$개 이하로 남으면 모든 사탕을 가져간다. 훔쳐지는 사탕보다 내가 먹는 사탕이 상자의 반 이상이 되도록하는 $k$값의 최소값을 구하는 문제다.
$k$를 파라메트릭으로 찾으면 된다. 결정함수는 기껏해야 매 번 500번 이하로 계산되기 때문에 (10^18 * 9^500 < 1) O($logn$)으로 봐도 무관하다.
XX XX OX XO
XO OX XX XX
총 4 모양으로 놓을 수 있는 L모양의 블럭이 있다. $2*n$크기의 게임판이 주어질 때 L모양의 블럭을 최대 몇 개 놓을 수 있는지 구하는 문제다.
$n$개의 줄을 봤을 때, 그 줄의 2칸이 모두 비어있을 경우에만 블럭을 놓아보자. 2칸이 모두 비어있는 줄의 왼쪽 줄의 칸 중 하나라도 비어있을 경우 그 방향으로 L모양을 배치하고, 아니면 오른쪽 줄의 칸 중 하나라도 비어있을 경우 그 방향으로 L모양을 배치하자. 너무 greedy하지만 어느 예외도 발생하지않는다.
숫자열이 주어진다. 숫자열의 부분숫자열의 개수를 구하는 문제다. 여기서 부분숫자열이란, 원래 숫자열에서 한번이라도 나온 숫자들을 적어도 1번 나와야하며, 제일 앞의 수가 0이 될 수 없다. 또한, 서로 다른 숫자의 순서를 섞어놓아도 서로 다른 숫자열로 판단한다.
한 번이라도 나온 숫자들을 모두 배열에 넣어놓은 뒤, 두 번 이상 나온 숫자들을 하나씩 추가해가면서 완전탐색을 해버리면 된다. 중복숫자를 포함한 배열에 대해 숫자를 섞어 만들 수 있는 숫자의 개수는 $n! / (\prod x!)$(여기서 $x$는 각 중복숫자의 개수)로 계산할 수 있고, 0이 제일 앞에 있는 경우도 위 식과같이 간단하게 해결가능하다.
재귀로 짜게될 경우 중복해서 같은 배열를 세는 경우가 발생하는데, set<vector<int>>를 이용한 memoization으로 이미 계산한 배열은 중복계산하지 않도록 처리해주어야한다.
