본문 바로가기

백준

 (223)
[ICPC] 백준 11501 - 주식 https://www.acmicpc.net/problem/11501 힌트(시간 초과 관련) 더보기 이 문제는 $O(N)$으로 풀 수 있다. 당신은 이미 계산했던 날을 다시 거쳐갈 필요가 없음을 상기하라. 풀이 더보기 각 날마다 주식의 가격이 주어졌을 때 최대 이득을 취하는 방법을 찾아야 한다. 우리는 이미 어느 날에 가격이 높은지 알고 있다. 다음 개형을 보자. 이런 형태에서는 1~2일에 매수하고 3일에 매도, 4~5일에 매수하고 6일에 매도하는 게 최적해가 됨을 단박에 알 수 있다. 다음 개형도 보자. 이런 경우는 1~5일까지 매수를 하다가 6일에 전부 매도하는 게 최적해가 된다. 이 두 개형을 통해 우리는 주식 가격의 극대 값에 도달하기 전까지 매수를 해야 함을 발견할 수 있다. 그렇다면 이를 어떻게..
백준 1439 - 뒤집기 https://www.acmicpc.net/problem/1439 힌트 더보기 1로 만들기 vs 0으로 만들기 둘 중 최소가 되는 횟수가 최적해이다. 풀이 더보기 모든 수를 1로 만들거나 0으로 만들어야 한다. 어떻게 하면 최소가 될 수 있는지 알 수 있을까? 문제에서 이야기한 전체를 뒤집는 것은 사실 의미 없는 행동이다. 문자열에서 0의 묶음 개수를 x, 1의 묶음 개수를 y라고 할 때 전체를 뒤집으면 x랑 y의 값이 서로 뒤바뀔 뿐이기 때문이다. 그러면 우리는 각 묶음의 개수 중 최소가 바로 정답이 됨을 깨달을 수 있다. 구현의 편의를 위해 erase를 사용하여 중복 문자열을 없애버린 뒤 0과 1이 나타나는 횟수를 각각 세서 그중 최소를 출력하면 된다. 전체 코드 #include using names..
백준 2423 - 전구를 켜라 https://www.acmicpc.net/problem/2423 힌트 더보기 0-1 BFS를 이용하면 가중치가 0과 1로만 이루어진 그래프에서 $O(V + E)$의 시간복잡도로 문제를 해결할 수 있다. 이를 문제에 형태에 맞춰 구현하는 방법을 생각해본다. 만약 문제를 틀린 상태에서 이 게시글을 보고 있는 것이라면 다음 격자로 갈 수 있는 조건을 다시 확인해보도록 하자. 풀이 더보기 문제에 주어진 회로는 최대 8방향으로 탐색할 수 있음을 보여주고 있다. 그리고 회로가 가질 수 있는 위상은 두가지이므로 좌표와 위상을 나타내는 3차원 배열을 생성해서 회로를 돌렸을 때 가중치를 1로 생각해서 0-1 BFS를 수행하면 된다. 다만 회로를 돌린다고 무조건 갈 수 있는 것이 아니다. 다음 두 경우를 보자. 왼쪽의 ..
[USACO] 백준 6156 - Cow Contest https://www.acmicpc.net/problem/6156 힌트 더보기 어떤 소의 순서를 정확히 알기 위해선 자기보다 낮은 스킬의 소와 높은 스킬의 소의 합이 n - 1마리가 되어야 한다. 각 소들의 sparse 한 스킬 관계를 그래프 형태로 정리하는 방법을 생각해본다. 풀이 더보기 소의 순서를 확정하기 위해선 자기보다 높은 스킬의 소가 몇 마리인지, 자기보다 낮은 스킬의 소가 몇 마리인지 알아야 한다. 하지만 입력은 서로 두 소의 상하 관계만이 주어졌을 뿐이다. 파편화된 관계를 가지고 전체 순위를 알 수 있는 방법이 있을까? 사실 순위가 몇위인지 아는 건 딱히 중요하지 않고 순위가 있다는 것을 알아내기만 하면 된다. 각 관계를 높은 스킬의 소가 낮은 스킬의 소로 향하는 단방향 간선을 가진 그래프..
백준 12844 - XOR https://www.acmicpc.net/problem/12844 힌트 1 더보기 세그먼트 트리의 lazy propagation을 이용하여 특정 구간에 대한 연산을 $O(logN)$ 시간 복잡도로 적용할 수 있다. 힌트2 더보기 xor의 연산 기호가 $\oplus$이고 임의의 원소 A에 대해 $A \oplus A = 0$ $A \oplus 0 = A$ 이다. 이 성질을 lazy propagation에 적용할 수 있는가? 풀이 더보기 1번 쿼리를 보면 lazy propagation을 응용해야 하는 것을 알 수 있다. xor 연산을 어떻게 적용할까? xor의 두 성질을 짚고 가자. $A \oplus A = 0$ $A \oplus 0 = A$ 이 성질을 통해 같은 수를 홀수 번 xor하면 A, 짝수 번 xo..

티스토리툴바