백준 문제풀이
백준 21735 - 눈덩이 굴리기 [C++/Python]
Vermeil
2021. 5. 23. 22:43
https://www.acmicpc.net/problem/21735
21735번: 눈덩이 굴리기
눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은
www.acmicpc.net
비트마스킹
0이면 2칸, 1이면 1칸 이동
Python 코드
|
1
2
3
4
5
6
7
8
9
10
11
|
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)
|
cs |
c++ 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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;
}
|
cs |
