본문 바로가기

분류 전체보기

 (236)
C++[백준] 11377 열혈강호 3 https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 솔루션 라이님은 천재다. 다른 열혈강호 문제에서, 해당 문제는 K명이 일을 최대 2개 할 수 있다고 한다. 이를 해결하는 방법은, 첫번째는 열혈강호를 풀듯이 풀고, K번만큼 이분매칭을 또 하는 것이다. 나는 아직 머리가.. 안좋아서, 증명은 안되지만 보고 감탄을 뱉었다. 코드 #include #include using namespace std; int N..
C++[백준]11376 열혈강호 2 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 솔루션 열혈강호와 문제는 비슷한데, 각 사원이 최대 2개의 일을 수행 할 수 있다고 한다. 열혈강호와 솔루션은 똑같고, 이분 매칭을 2번 호출하면 된다. 코드 #include #include using namespace std; int N, M; vector Inhole[1002]; vector V[1002]; int is_visit[1002]; bool dfs(int cur) { is..
C++[백준]1298번 노트북의 주인을 찾아서 https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 이전 코드를 참고하지 않고 풀어보려고 노력했는데, 역시 틀렸다. 왜지? 열심히 뇌버깅을 돌려 본 결과, 틀린 지점을 찾을 수 있었고, 이를 고쳐 AC를 받았다! (어쩌면 이분매칭 쉬울지...도..? 농담이고 안깝치겠습니다.) 솔루션 각각의 사람이 b번의 노트북을 가져 갈 수 있다고 벡터에 넣어둔다. 그리고, 각각 이분매칭을 시작하는데, 먼저 매칭이 가능한 노트북이 있다면, 매칭을 시켜준다. 매..
C++[백준]11375번 열혈강호 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 솔루션 이전에, https://www.acmicpc.net/problem/14750를 선배에게 받아서 선배가 다 도와줘서 풀 뻔한(아직 못품.. ㅎㅋ) 문제인데 이 문제는 네트워크 플로우도 가능하지만, 테스트 케이스가 작아서 이분매칭으로도 가능하다고 해서, 여기에 있는 코드를 참고하니까, 이것도 쉽게 풀렸다. 각 회사원이 가능한 작업의 인덱스를 벡터에 담는다. 그리고 이분매칭을 통해서 이분..
C++[백준]9576번 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 솔루션 현재 컨닝이라는 문제를 보다가 컨닝 2 문제는 이분 매칭으로 풀 수 있다고 하여, 이분 매칭에 대해서 공부 중이다. 아직 명확한 설명은 어렵다. 이론은 각각 배급 받을 책의 범위를 입력을 받는다. (pair 로 받았다.) 그리고 각 M개에 대해서, 이분 매칭을 시킨다. 각각 범위에 배급 받을 수 있는 책이 있다면 책을 배급 받는다. 만약 배급 받을 수 있는 책이 없다면, 내가 배급 받을 수 있..
C++[백준]10974번 모든 순열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 솔루션 재귀를 통해 쉽게 해결 할 수 있는 문제. N과M 처럼 벡터를 선언하고 각 깊이마다 아직 방문하지 않은 숫자에 대해서 벡터에 값을 넣어주고 방문 처리를 한다. 그리고 함수를 재귀적으로 호출하면 된다. 코드 #include #include using namespace std; int N; bool is_visit[10]; vector V; void printSeq(int deep) { if (deep == N) { for (auto& v : V) cout
C++[백준]15661번 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 솔루션 모든 값들을 2차원 배열에 입력을 저장한다. 그리고 A팀에 포함을 시키거나, B팀에 포함을 시킬 수 있는데, 나는 팀에 포함 시키는 것은 벡터를 통해 해결하였다. 그리고 깊이가 N까지 커졌다면, 그때 각 팀의 점수를 이중for문을 통해 값을 구하였다. 그런데,,, a팀, b팀의 인원수를 맞춰야 하는 줄 알았으나.. 극단적인 예로, a팀에 2명, ..
C++[백준]15649번 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 솔루션 깊이 우선 탐색으로 문제를 접근했다. 각각 특정 수를 방문 했다면 방문처리를 해 주었고, 방문한 숫자는 차례대로 벡터에 넣어주었다. 그리고 깊이가 M 만큼 높아졌다면, 그 떄, 벡터에 담긴 수를 출력을 한다. 그리고 다시 리턴 되면, 방문 처리를 비워주고, 벡터에 담긴 것도 뺴 준다. 코드 #include #include using namespace std; int N, M; vector..

티스토리툴바