joseph0528 코딩 블로그

solved.ac 티어 : 플래티넘 2 www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net bfs를 사용해서 각 자동차(C)마다 모든 주차구역(P)과의 거리를 저장해주고 이분 탐색하면서 이분 매칭으로 나올 수 있는 최솟값을 찾아주면 된다. 이분 탐색은 mid가 있을 때 각 자동차마다 주차구역을 가는 거리가 mid이하인 값들만 가지고 이분 매칭을 해주면 된다. 이때 이분매칭 했을 때의 값이 자동차 개수와 동일하다면 mid와 저장되어있는 최솟값을 비교하여 더 작을 ..

solved.ac 티어 : 플래 2 www.acmicpc.net/problem/2570 2570번: 비숍2 서양장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같이 크기가 5인 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 www.acmicpc.net 이문제는 joseph0528.tistory.com/30 BOJ 9525(룩 배치하기)풀이 solved.ac 티어 : 플래 3 www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형 joseph0528.tistory...

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이 www.acmicpc.net 이 그림은 노란색 행을 선택했을 때 선택될 수 있는 초록색 열이다. 이 그림은 파란색 행을 선택했을때 선택될수 있는 보라색 열이다. 이거처럼 행을 기준으로 나올 수 있는 열에 번호를 매겨서 이분 매칭을 해주면 된다. 위 그림을 번호를 매겨 줬을 때 빨간색은 1, 주황색은 2, 노란색은 3, 초록색은 4, 하늘색은 5, 보라색은 6, 핑크색은 7로 잡아주고(..

solved.ac 티어 : 플래 4 www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net 이문제는 입력에 음수가 있기 때문에 평범한 이분 매칭으로는 안된다. 그렇다고 음수에다가 값을 더하려고 해도 범위가 -10^6

solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/1574 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼 www.acmicpc.net 이문제는 한 행 과열에 단 한 개의 룩을 놔서 최대한 많이 놓은 개수를 출력하는 문제이다. 정말 간단한 이분 매칭 문제다. 행과 열에 한 개만 놓을 수 있다는 것은 행 또는 열을 잡고 자신이 놓을 수 있는 곳에 이분 매칭을 해주면 된다. 하지만 여기서 빈칸이 생기는데 그래도 공격이 막히지는 않으니 입력 위치가 아니면서 놓을 수 있는 곳들을 이분 매칭 해주면 된다...

solved.ac 티어 : 플래티넘 5 www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 이문제는 아주 쉬운 이분 매칭이라 입력을 받고 너비가 w/2 이상 w*3/4 이하랑 너비가 w 이상 w*5/4인 경우 해당 위치에 값을 넣어주고 이분 매칭 하면 끝난다. (이 문제 못 풀면 이분 매칭 다시 배워야 된다.) #include #include #include #include #include using namespace std; typedef..

이분 매칭 문제입니다. solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 이문제는 입력받은 것을 2중 반복하면서 자신이랑 위치가 다른 곳 중에서 둘이 더했을 때 소수일 때만 배열에 넣어주고 배열에서 첫 번째 위치의 배열에 들어있는 수 개수만큼 반복하면서 첫 번째 수랑 더했을 때 소수가 되는 수들이랑 첫 번째 수를 하나하나 빼면서 나머지 수들로 전부다 짝이 만들어질 경우 배열..

기본적인 이분매칭이었습니다. solved.ac 티어: 플래티넘 3 www.acmicpc.net/problem/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net 일단 이문제는 이분매칭 문제이기 때문에 이분매칭을 할수있어야 한다. 열혈강호 문제를 풀어보고 오자. www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각..