본문 바로가기
반응형

Problem Solving/BOJ228

백준 14391번 종이 조각 - C++ 풀이 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를.. 2022. 8. 23.
백준 13904번 과제 - C++ 풀이 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1781번 컵라면 문제와 동일한 문제이다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (점수=컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include using namespace std; typedef pair pii;.. 2022. 8. 22.
백준 1963번 소수 경로 - C++ 풀이 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다. #include #include using namespace std; const int INF = 987654.. 2022. 8. 20.
백준 17142번 연구소 3 - C++ 풀이 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; typedef pair pii; const int EMP.. 2022. 8. 19.
백준 25430번 다이제스타 - C++ 풀이 1. 다익스트라를 사용하여 최단거리를 구한다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해 두고 더 큰 가중치의 간선만 사용하도록 한다. 3. 같은 노드에 도착하더라도 w에 따라 이용할 수 있는 다음 간선이 달라지므로 dist 배열은 dist[node][w]의 형태로 운영한다. 1. 다익스트라를 사용하여 최단거리를 구한다. 다익스트라 알고리즘을 사용하여 두 노드 사이의 최단거리를 구할 수 있다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해두고 더 큰 가중치의 간선만 사용하도록 한다. 단, 문제에서 주어진 조건에 따라 경로 내 간선의 가중치는 오름차순이 되어야 한다. 따라서 다익스트라 과정에서 이 조건을 만족할 수 있도록 마지막으로 이용한 간선의 가중치 w.. 2022. 8. 18.
반응형

티스토리툴바