Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 구현
  • 정수론
  • 문자열
  • 트라이
  • 이분탐색
  • 정렬
  • 그래프
  • 수학
  • 스택
  • 누적합
  • 동적계획법
  • 조합론
  • 큐
  • 유니온 파인드
  • UC++
  • 위상 정렬
  • 브루트포스
  • 분할정복
  • SCC
  • 트리
  • LCA
  • 우선순위큐
  • 백트래킹
  • 백준
  • 기하
  • KMP
  • C++
  • 세그먼트 트리
  • 투포인터
  • 최소 스패닝 트리

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 1311번 문제
공부 및 정리/백준 코드

[C++]백준 - 1311번 문제

2021. 11. 3. 16:39

1311번: 할 일 정하기 1 (acmicpc.net)

 

1311번: 할 일 정하기 1

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매

www.acmicpc.net

 

1311번 : 할 일 정하기 1


N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.

Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력


첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.

 

 

출력


모든 일을 하는데 필요한 비용의 최솟값을 출력한다.

 

 


 

생각해 볼 점


DP 문제입니다. 그런데, 평범한 DP와는 다르게 비트마스킹 기법을 이용합니다.

 

DP의 인덱스에 이진법을 넣는다고 생각해봅시다.

 

DP[ 111 ] 과 같이 이진법이 들어갔다면 비트마스킹 기법을 이용하여 DP 배열을 이용할 수 있습니다.

 

DP[i][bit] = i번 째 사람이 bit의 경우의 수를 만났을 때 최솟값을 저장한다.

 

예시)

 

DP[0][4] = 0번 째 사람이 4의 경우의 수를 만났을 때의 최솟값

 

4 = 이진법으로 100입니다.

 

위의 사진 과 같이, 자릿수에 맞는 일이 선택 가능한지 아닌지를 판단하여

 

4의 경우에는 0번째, 1번째 일이 아직 남아있을 때를 의미합니다.

 

DP[0][4] = 0, 1번째 일을 택할 수 있을 경우 최솟값을 저장합니다.

 

이렇게 비트 연산을 통해 DP 알고리즘을 이용하여 정답을 도출할 수 있습니다.

 

코드


#include <iostream>
using namespace std;

int N;
int **dp;
int **works;

//DP[i][비트마스크]의 최소값을 반환하는 함수
int solve(int i, long long bit)
{
    if(i == N) return 0;
    if(dp[i][bit] != 0) return dp[i][bit];
    
    long long current;
    int ret = 200000;
    for(int j = 0; j < N; j++)
    {
        current = 1 << j;
        if(!(bit & current)) 
        {
            bit += current;
            int result = works[i][j] + solve(i + 1, bit);
            if(result < ret) ret = result;
            bit -= current;
        }
    }
    
    return dp[i][bit] += ret;
}


int main() 
{
    scanf("%d", &N);
    
    long long Max_bit = 0;
    
    //비트 마스킹용
    for(int i = 0; i < N; i++) Max_bit += 1 << i;
    works = new int*[N];
    dp = new int*[N];
    
    for(int i = 0; i < N; i++)
    {
        works[i] = new int[N];
        dp[i] = new int[Max_bit + 1];
        fill_n(dp[i], Max_bit + 1, 0);
        for(int j = 0; j < N; j++) scanf("%d", &works[i][j]);
    }
    
    printf("%d", solve(0, 0));
    
    for(int i = 0; i < N; i++) 
    {
        delete[] works[i];
        delete[] dp[i];
    }
    delete[]works;
    delete[] dp;
	return 0;
}

 

그 외


비트마스킹의 특성 상 입력 값이 커지면, 용량이 지나치게 많이 필요하게 되어 사용할 수 없습니다.

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 2098번 문제  (0) 2021.11.04
[C++]백준 - 17472번 문제  (0) 2021.11.04
[C++]백준 - 2357번 문제  (0) 2021.11.03
[C++]백준 - 11505번 문제  (0) 2021.11.01
[C++]백준 - 2042번 문제  (0) 2021.11.01
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 2098번 문제
    • [C++]백준 - 17472번 문제
    • [C++]백준 - 2357번 문제
    • [C++]백준 - 11505번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바