[코테오답] 시프트 연산 결과 대입

Link : https://www.acmicpc.net/problem/1094

Level : S3

유형 : 비트마스킹

 

---

📌 문제 탐색

길이가 64인 막대기를 잘게 나누고 붙이며, 원하는 길이(X)로 만드는 것이 목표다.

 

📌 코드 설계하기

필요한 변수는 현재 짧은 막대, 합에 대한 2가지 변수 필요하다.

 

1. 원하는 길이 X 입력 받기

2. for문의 i 변수는 짧은 막대 길이 변수다. sum은 막대 길이 합(모든 막대) 변수다. 

3. 반복문을 돌 때 경우는 3가지다.

• case 1 : 현재 막대 길이가 원하는 길이보다 크면 sum은 재정의된다. (sum=i)
  남은 막대 버리니까 이후 코드는 실행 X (continue)
• case 2 : 현재 막대 길이 합이 원하는 길이보다는 작은데, 현재 가장 작은 막대 i를 더했을 때 원하는 막대길이 보다 커지는 경우 그
  작은 막대는 무시 (continue)
• case 3 : 현재 막대 길이 합이 원하는 길이보다 작은데, 현재 가장 작은 막대 i를 더했을 때 원하는 막대길이보다 작거나 같은 경우 그 작은 막대를 더한다. (sum += i)

 

📌 정답코드

#include <iostream>
using namespace std;


int x, cnt=1;

int main(){

    cin >> x;

    int sum = 64;
    for(int i = 32; i>0; (i >>= 1)){

        if(sum == x) break;

        //---------------------

        //case1.업데이트(재정의)
        if(sum > x){
            sum=i;
            continue;
        }else if(sum < x){
            if(sum + i > x) continue;    //case2.무시하고 지나감(안더함)
            else sum += i;               //case3. 누적합
        }

        cnt++;

    }

    cout << cnt << "\n";
    return 0;
}

 

📌 오답노트

시프트 연산 결과 대입 문제

for(int i = 32; i>0; (i >> 1))

 

처음 작성한 코드이다. (i >> 1)은 right shift 계산만 할 뿐, 그것이 다시 i에 반영되지 않는다!!!

따라서 shift 연산 결과를 다시 i에 대입해줘야 한다.

for (int i = 32; i > 0; i >>= 1) {
    // i = i >> 1 의 축약 형태
    ...
}