Skip to main content

2311 - Longest Binary Subsequence Less Than or Equal to K

info

풀이 키워드​

스포주의

그리디 DP


풀이 코드​

info
  • 메모리: 41320 KB
  • 시간: 1 ms
class Solution {
    public int longestSubsequence(String s, int k) {
        int sum = 0;
        int ans = 0;
        int bits = (int)(Math.log(k) / Math.log(2)) + 1;
        char[] sArr = s.toCharArray();
        for (int i = 0; i < sArr.length; ++i) {
            char ch = sArr[sArr.length-1-i];
            if (ch == '1') {
                if (i < bits && sum+(1<<i) <= k) {
                    sum += 1<<i;
                    ++ans;
                }
            }
            else {
                ++ans;
            }
        }

        return ans;
    }
}

풀이 해설​

int bits = (int)(Math.log(k) / Math.log(2)) + 1;

k를 이진수로 표현했을 때 필요한 자리수를 상단의 공식으로 구한다.

다만 알아둘 점이라면,

log⁡2k=ln⁡kln⁡2\log_2 k = \frac{\ln k}{\ln 2}

자바의 로그는 자연로그이기 때문에 밑 변환 공식을 사용하여 구해야 한다.

+1을 마지막에 하는 이유는 몇 개 직접 계산해보면 알 수 있다.

자리수 계산 예
3 -> 0b11  -> 2자리
4 -> 0b100 -> 3자리
5 -> 0b101 -> 3자리

이렇듯, ⌊log⁡23⌋+1=2,⌊log⁡24⌋+1=3,⌊log⁡25⌋+1=3\lfloor \log_2 3 \rfloor + 1 = 2, \quad \lfloor \log_2 4 \rfloor + 1 = 3, \quad \lfloor \log_2 5 \rfloor + 1 = 3 이므로 +1 해줘야 한다.

나머지는 WIP 세미나 들어서 피곤함


메모​

  • 실전이면 안전빵으로 DP 풀이했을 것 같음... (그렇게도 풀어보라는 것)