넘치게 채우기

https://codeforces.com/contest/2064/problem/DCodeforces Round 1005(Div. 2) - D. Eating문제 유형: 그리디, 비트마스킹, 이진 탐색시간 제한: 5초메모리 제한: 512MB 문제There are n">n slimes on a line, the i">i-th of which has weight wi">wi. Slime i">i is able to eat another slime j">j if wi≥wj">wi≥wj; afterwards, slime j">j disappears and the weight of slime i">i becomes wi⊕wj">wi⊕wj.The King of Slimes wants to ru..

https://leetcode.com/problems/construct-smallest-number-from-di-string/description/leetcode - Construct Smallest Number From DI String문제 유형: 백트래킹, 비트마스킹, 문자열 처리, 그리디문제 난이도: Medium 문제You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.A 0-indexed string num of length n + 1 is created using the following conditions:num..

https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/leetcode - Construct the Lexicographically Largest Valid Sequence문제 유형: dfs, 재귀, 백트래킹, 비트마스킹문제 난이도: Medium 문제Given an integer n, find a sequence that satisfies all of the following:The integer 1 occurs once in the sequence.Each integer between 2 and n occurs twice in the sequence.For every integer i ..

https://www.acmicpc.net/problem/2098BOJ - 외판원 순회문제 유형: TSP(외판원 순회), 비트마스킹, 다이나믹 프로그래밍, dfs문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 ..

https://www.acmicpc.net/problem/1562BOJ - 계단 수문제 유형: 다이나믹 프로그래밍, 비트마스킹문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이0~9이므로, 등장여부 상태를 비트마스킹을 이용할 수 있다. (처음에 상태추적을..

https://www.acmicpc.net/problem/9527BOJ - 1의 개수 세기문제 유형: 누적합, 수학, 비트마스킹문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. ∑x=ABf(x)\[\sum_{x=A}^{B}{f(x)}\]  입력첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력1의 개수를 세어 출력한다. 풀이어떤 수 2^i-1에 대한 점화식은 다음과 같다: pows[i]는 (1  i비트의 ..

https://leetcode.com/problems/neighboring-bitwise-xor/description/leetcode - Neighboring Bitwise XOR문제 유형: 비트마스킹, 그리디문제 난이도: Medium 문제A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.Specifically, for each index i in the range [0, n - 1]:If i = n - 1, then derived[i] = original[i] ⊕ original[0].Otherwise..

https://leetcode.com/problems/bitwise-xor-of-all-pairings/description/leetcode - Bitwise XOR of All Pairings문제 유형: 비트마스킹문제 난이도: Medium 문제You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. There exists another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer ..

https://leetcode.com/problems/minimize-xor/description/leetcode - Minimize XOR문제 유형: 비트마스킹, 그리디문제 난이도: Medium 문제Given two positive integers num1 and num2, find the positive integer x such that:x has the same number of set bits as num2, andThe value x XOR num1 is minimal.Note that XOR is the bitwise XOR operation.Return the integer x. The test cases are generated such that x is uniquely determine..

https://www.acmicpc.net/problem/1182BOJ - 부분수열의 합문제 유형: 브루트포스, 백트래킹, 비트마스킹문제 난이도: Silver II시간 제한: 2초메모리 제한: 256MB 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이백트래킹 또는 비트마스킹으로 풀 수 있다.백트래킹으로 ..