백준 13249 공의 충돌

문제

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

문제 풀이

2가지 상태 왼쪽 오른쪽으로 최대 12개이니 2^12로 풀 수있다 수가 너무 크니 비트마스킹을 이용하면된다.

너무 어려웠지만 같이 스터디하는분이 많이 도와주셨다..

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {

                for (int k = 0; k < n; k++) {
                    if (i & (1 << k)) {

                        if (a[j] < a[k] && a[j] + t >= a[k] - t) cnt++;
                    }
                }
            }
        }
    }

핵심 소스이다 모든 n에 대해서 비트마스킹을 하면서 j를 오른쪽 k를 왼쪽으로 보면서 달려가면된다 마지막에 1 0일경우 살펴보는데 당연히 k가 더 크면 j는 오른쪽으로 가고 k는 왼쪽으로 가니 충돌한다

다음 경우 !!! -> j가 어느정도까지는 커도된다 어디까지? + t해서 >=가 됐을 경우는 충돌된 상태로 본다

소스

#include <bits/stdc++.h>

using namespace std;

int n, t;
int a[13];  // 최대12개이니 2^12, 오 or  왼으로가능 
int main() {

    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cin >> t;
    int cnt = 0; //카운트 , 
    for (int i = 0; i < (1 << n); i++) {

        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {

                for (int k = 0; k < n; k++) {
                    if (i & (1 << k)) {

                        if (a[j] < a[k] && a[j] + t >= a[k] - t) cnt++;
                    }
                }
            }
        }
    }

    double ans = (double)cnt / (1 << n);
    cout << ans;
    return 0;
}