[선린 알고리즘 연구반] 알고리즘 기초 연습 #7

작성일 | In


재제출 죄송합니다.

집합

문제 링크

  • http://icpc.me/11723

풀이

set으로 해도 되고, bitmask로 해도 되고~~

부분 수열의 합

문제 링크

  • http://icpc.me/1182

풀이

0 : 원소를 포함 안함 / 1 : 원소를 포함함
으로 각 원소를 비트로 관리

1
2
3
4
5
6
7
8
9
10
11
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++;
}

N과 M(1)

문제 링크

  • http://icpc.me/15649

풀이

백트래킹 뚝-딱

발전소

문제 링크

  • http://icpc.me/1102

풀이

dp[n][bit] = 현재 n번 발전소를 보고 있고, 현재 켜져 있는 발전소가 bit일 때 최소 비용

외판원 순회

문제 링크

  • http://icpc.me/2098

풀이

dp[n][bit] = 현재 n번 정점에 있고, 방문 상태가 bit일 때 최소 비용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f(int now, int bit){
	int &ret = dp[now][bit];
	if(ret != -1) return ret;
	if(bit == (1<<n)-1){
		if(g[now][0]) return ret = g[now][0];
		else return ret = 1e9+7;
	}

	ret = 1e9+7;

	for(int i=0; i<n; i++){
		if(bit & (1<<i)) continue;
        if(!g[now][i]) continue;
		ret = min(ret, f(i, bit | (1<<i)) + g[now][i]);
	}
	return ret;
}

계단 수

문제 링크

  • http://icpc.me/1562

풀이

dp[n][i][bit] = 길이가 n이고, 맨 뒤에 있는 숫자가 i, 숫자 출현 상태가 bit인 경우의 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f(int len, int num, int bit){
	int &res = dp[len][num][bit];
	if (res != -1) return res;
	if (len == n){
		return res = bit == ((1 << 10) - 1);
	}

	res = 0;
	if (num - 1 >= 0){
		res += f(len + 1, num - 1, bit | (1 << (num - 1)));
	}
	if (num + 1 < 10){
		res += f(len + 1, num + 1, bit | (1 << (num + 1)));
	}
	res %= mod;
	return res;
}

달이 차오른다, 가자.

문제 링크

  • http://icpc.me/1194

풀이

열쇠 상황을 bit로 표현한 뒤 BFS

보석 줍기

문제 링크

  • http://icpc.me/2001

풀이

보석의 번호를 1 ~ K로 지정한 뒤, 보석 보유 상황을 비트로 표현해서 BFS