BOJ 문제풀이2

1920 수찾기

주어진 배열 A를 정렬해두고 M개의 숫자가 그 안에 있으면 1 없으면 0을 출력해주면 됩니다

다만 N이 10만이라 $O\left ( N^2 \right )$이 아니라 $O\left ( NlogN \right )$안에 해결하기 위해 이분탐색을 이용해 수를 찾아줘야 합니다

if (binary_search(all(A), tmp)) cout << 1 << endl;
else cout << 0 << endl;

 

1654 랜선 자르기

랜선 길이의 제한이 21억을 넘어 int형의 max값입니다

단순히 랜선 길이를 1부터 시작해서 21억까지 보면서 N개로 자를 수 있는지 확인해서는 안됩니다

길이를 기준으로 봤을때 랜선을 N개로 나눌 수 있는 어떤 길이 I를 기준으로 I보다 작을때는 무조건 N개 이상으로 랜선을 나눌 수 있다는 사실을 통해 최적화 문제임을 알 수 있고, 이는 이분탐색을 통해 해결 할 수 있습니다

F(X) :=  랜선을 최대 길이 X로 자를 때, 나눠진 랜선의 갯수가 N 이상이면 true 아니면 false

 

while (lt+1<rt) {
        ll mid = (lt+rt)/2;
        if (F(mid)>=k) lt=mid;
        else rt=mid;
    }

실제 구현은 int를 반환해서 K보다 큰지 작은지를 판단했습니다

 

1260 DFS와 BFS

방문하게되는 정점들을 전위로 찾아주는 문제입니다

dfs에서 습관적으로 후위탐색을 해줬는데 이 부분만 주의해 주시면 쉽게 해결 할 수 있습니다

 

2636 치즈

그래프 탐색을 하면서 치즈가 있는 부분을 녹여주면 됩니다

총 몇번의 탐색이 있었는지 카운팅을 해주면서, 이때 치즈가 다 녹았는지 확인할 때 남아있는 치즈의 갯수를 같이 구할 수 있습니다

저는 BFS를 통해 이를 구현했는데 DFS로도 해결 가능할 것 같습니다

if (!vis[nxtX][nxtY]) {
	vis[nxtX][nxtY]=true;
	if (B[nxtX][nxtY]==0) pq.push({nxtX, nxtY});
	else B[nxtX][nxtY]=0;
}

치즈는 이렇게 녹여주면 됩니다