비트마스킹7 백준 1086 / C++ https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net [ 풀이 ] N이 작고 순열의 각 원소의 순서가 중요하므로 비트DP로 순회하자. p1 p2 .... pn 순으로 간다고 하자. p1에서 p2로 갈 때 수는 p1*10^(p2의 길이)+p2 가 된다. p2의 길이는 최대 50이므로 단순 계산으론 안되고 미리 10^m (modk)를 전처리해놓으면 된다. p_i들 또한 k로 나눈 나머지만 중요하므로 순회하면서 모두 k로 나눈 나머지로 전처리해놓자. 이제 dp식을 세우자. dp[bit][v]는 .. 2022. 8. 4. 백준 6062 / C++ https://www.acmicpc.net/problem/6062 6062번: Mixed Up Cows Each of Farmer John's N (4 2022. 7. 21. 백준 1062 / C++ https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [ 풀이 ] anta와 tica는 디폴트로 가르쳐야 한다. 이 5개를 제외한 글자를 가르치자. 알파벳이 26개이니 그냥 브루트포스로 21C(k-5)개를 골라주면 된다. k-5개를 골라 가르친 후에 N개의 문자열을 읽을 수 있는지 확인해주면 된다. sol 1) 그냥 모든 문자열을 순회하며 읽을 수 있는지 판별한다. 총 시간복잡도는 O(21Ck-5 * N*15)이고 이 값의 최대는 대충 21C.. 2022. 7. 15. 이전 1 2 다음