백준 21735 - 눈덩이 굴리기 [C++/Python]

https://www.acmicpc.net/problem/21735

21735번: 눈덩이 굴리기

 

비트마스킹

0이면 2칸, 1이면 1칸 이동

 

Python 코드

n,m=map(int,input().split())
a=list(map(int,input().split()))
s=0
for i in range(1<<m):
    x=1;b=0
    for j in range(m):
        if i&(1<<j):b+=1;x>>=1
        if j+b>=n:break
        x+=a[j+b]
    s=max(s,x)
print(s)

c++ 코드

#include <algorithm>
#include <iostream>
#define endl '\n';
 
using namespace std;
 
int a[100];
 
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
 
    int bit = 1 << m;
    int bc, now;
    int ans = 0;
    for (int i=0;i<bit;i++){
        now = 1;
        bc = 0;
        for (int j=0;j<m;j++){
            if (i & (1 << j)){
                bc += 1;
                now >>= 1;
            }
            if (j + bc >= n) break;
            now += a[j + bc];
        }
        ans = max(ans, now);
    }
    cout << ans << endl;;
    return 0;
}