넘치게 채우기

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가 되는 부분수열의 개수를 출력한다. 풀이백트래킹 또는 비트마스킹으로 풀 수 있다.백트래킹으로 ..

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/description/leetcode - Flip Columns For Maximum Number of Equal Rows문제 유형: 비트마스킹, 행렬문제 난이도: Medium 문제You are given an m x n binary matrix matrix.You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).Return the maximum number of..

https://www.acmicpc.net/problem/1987BOJ - 알파벳문제 유형: 백트래킹, dfs, 비트마스킹문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. ..

https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-ii/description/?envType=daily-question&envId=2024-11-10leetcode - Shortest Subarray With OR at Least K II문제 유형: 비트마스킹, 슬라이딩 윈도우문제 난이도: Medium 문제You are given an array nums of non-negative integers and an integer k.An array is called special if the bitwise OR of all of its elements is at least k.Return the length of the shortest s..

https://leetcode.com/problems/minimum-array-end/description/?envType=daily-question&envId=2024-11-09leetcode - Minimum Array End문제 유형: 비트마스킹문제 난이도: Medium 문제You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0  nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.Retu..