본문 바로가기

분류 전체보기414

백준 17834 사자와 토끼 문제 URL : https://www.acmicpc.net/problem/17834 17834번: 사자와 토끼 사자와 토끼는 전국적으로 인기를 끌고 있는 재밌는 보드게임이다. 사자와 토끼를 즐기기 위해서는 2명의 플레이어와 1명의 심판이 필요하다. 보드판은 N개의 수풀과 M개의 오솔길로 이루어져 �� www.acmicpc.net 문제 접근법: 사자와 토끼가 서로 어떻게 움직여도 영원히 게임이 끝나지 않는 경우의 수를 구하는면 된다 근데 어떻게 구하냐?? 꽤 오랫동안 생각한 문제였지만 이분그래프의 연장선 문제였습니다. 이분그래프가 무엇인지 모르겠다면 아래 이분그래프 설명했던 자료가 있으니 이것을 먼저 보고 오길 바랍니다. https://congsoony.tistory.com/11 백준 1707 이분그래프 .. 2020. 7. 26.
백준 1707 이분그래프 문제 URL : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 접근법: 물감의 색이 2개만 주어졌다고 생각하고 어떤 노드에서 출발해서 그노드와 인접한 노드들간에 서로 다른색으로 색칠이 되어있다면 그것은 이분그래프라고 생각하면 됩니다. 쉽게 그림으로 설명해드리겠습니다. 간단하게 1번노드에서 먼저 초록색을 색칠한다면 1번과 인접한 2,4번 노드에 노랑색을 색칠하고 또 2,4번과 인접한 5,6번에 초록색을 색칠하고 5,6번과 인접.. 2020. 7. 26.
백준 17835 면접보는 승범이네 문제 URL : https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 접근법: 다익스트라를 이용할줄 안다면 문제 접근하는건 크게어렵지 않습니다. 면접장까지의 거리가 가장 먼도시와 그거리를 구하기때문에 순방향으로 그래프를 그리셨다면 답은 구해질수 있을지 언정 시간이 굉장히 오래 걸립니다. 일일이 한집에서 면접장까지 구하기때문에 다익스트라를 여러번 돌려야하기 때문에 그렇다면 반대로 면접장까지 .. 2020. 7. 26.
백준 2812 크게만들기 문제 URL : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K > k; cin >> s; } int main().. 2020. 7. 22.

티스토리툴바