목록이분매칭 (1)
블로그 옮겼습니다
BOJ 1444번 숌 언어
https://www.acmicpc.net/problem/1444 하나의 단어는 알파벳 소문자하나와 대문자 하나로 이루어진다. 소문자가 앞에 나오는 경우와 뒤에 나오는 경우이렇게 두가지 경우가 있다. 알파벳 소문자와 대문자가 번갈아 나오는 문장이 입력으로 들어올 때이 문장은 몇 개의 단어로 이루어 질 것이다. 이 때 여러가지 케이스가 있을 텐데 그중 최소 단어 개수를 찾는 문제이다.예를 들어 aAbAc 가 있으면 aA, bB, Ac 로 이루어 졌을 수도 있고 aA, Ab, Ac 로 이루어 졌을 수도 있는 것이다. 이 문제는 결국 최소 정점 덮개 이다. 최소 정점 덮개란 이분 그래프에서 모든 간선이 자신과 접한 두 정점 중최소한 하나는 선택하도록 할 때 최소로 선택하는 정점의 수이다. 그니까 하나의 정점을..
Algorithm/Problem Solving
2017. 7. 9. 04:11