~~재제출 죄송합니다.~~

한수

문제 링크

http://icpc.me/1065

풀이

1부터 N까지의 수가 각각 한수인지 아닌지 판별해주면 됩니다.
숫자를 각 자리 별로 분리한 뒤, 인접한 두 수 차이가 모두 같은지를 판별해주면 한수인지 아닌지 판단할 수 있습니다.

덩치

문제 링크

http://icpc.me/7568

풀이

1이상 N이하인 자연수 i가 있을 때, i번째 사람에 대해 아래 작업을 수행합니다.

1이상 N이하이며 i가 아닌 자연수 j를 고릅니다.
i.height < j.height && i.weight < j.weight 를 만족하는 j의 개수 k를 구합니다.
k+1을 출력합니다.

부분수열의 합

문제 링크

http://icpc.me/1182

풀이

어떤 원소가 들어간다/들어가지 않는다 를 1/0 으로 나타낼 수 있습니다.
각각의 원소의 포함 여부를 비트로 나타낸다면 비스마스크로 행복하게 계산할 수 있습니다.

pow = 1 << n;
for(bit=0; bit<pow; bit++){
  sum = 0, isEmpty = 1;
  for(i=0; i<n; i++){
    if(bit & (1 << i)){
      sum += arr[i];
      isEmpty = 0;
    }
  }
  if(sum == s && !isEmpty) ans++;
}

Hard Ver.
Sol.

일곱 난쟁이

문제 링크

http://icpc.me/2309

풀이

9명의 난쟁이를 각각 비트로 생각하면 길이가 9인 이진수로 나타낼 수 있습니다.
켜져있는 비트가 7개인 경우에만 합을 계산해서 키의 합이 100인 경우의 수를 찾으면 됩니다.

int bitOnCnt(int a){
  int ret = 0;
  while(a){
    ret += (a&1);
    a >>= 1;
  }
  return ret;
}

알파벳

문제 링크

http://icpc.me/1987

풀이

지금까지 거쳐온 알파벳들을 체크해주면서 dfs를 돌면 됩니다.

퇴사

문제 링크

http://icpc.me/14501

풀이

두 가지의 방법을 떠올릴 수 있습니다.

스케쥴을 소화할 수 있게 상담을 잡는다.
대충 배치해둔 뒤, 스케쥴을 소화할 수 있는지 판단한다.

이 문제는 2번이 더 쉬워보이니 2번 방법대로 해봅시다.
대충 배치하는 것은 비트마스크를 이용해서 모든 경우를 한 번 씩 다 봐줍시다.
나중에 시작하는 상담이 앞에서 한 상담이 끝나기 전에 실행이 되면 소화 불가능한 스케쥴이라 생각해주면 됩니다.

pow = 1 << n;
for(bit=0; bit<pow; bit++){
  if(!can(bit)) continue;
  // something
}

체스판 다시 칠하기

문제 링크

http://icpc.me/1018

풀이

체스판을 8x8 사이즈로 자른 뒤, 왼쪽 위가 W인 경우와 H인 경우를 각각 고려해주면 됩니다.

리모컨

문제 링크

http://icpc.me/1107

풀이

임의의 채널로 이동을 한 뒤, +와 -를 이용해서 원하는 채널로 이동해줍시다.
모든 경우에서 최솟값을 찾아줍시다.

스도쿠

문제 링크

http://icpc.me/2580

풀이

0이 입력된 위치를 모두 배열에 저장해줍시다.
0이 입력된 모든 위치에 대해 naive하게 브루트포싱을 하면 TLE가 여러분을 반겨줍니다.
하나를 배치하고, 이렇게 배치해도 완성할 가능성이 있는지 판단하면서 최대한 가지치기를 많이 해주면 됩니다.