PS/백준

[ 백준 ] 15686번 : 치킨 배달 - ( C++/C/CPP )

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이법 ( 알고리즘 ) 처음엔 단순히 모든 치킨집과 집들의 거리를 계산해 그중 m개의 최소 수들을 구해 더했으나 tc부터 막혔다. 생각해보니 폐업을 시킨 후 도시의 치킨 거리를 구해야 하기 때문에 위의 방법은 틀린 방법이었다. 문제를 읽고 깊게 생각해보지 않으니 이런 황당한 실수를 하는 거 같다. dfs를 돌며 모든 치킨집에 대해 계산했다면 폐업시키지 않은 치킨집과 각 ..

[ 백준 ] 2583번: 영역 구하기

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이법 ( 알고리즘 ) 이차원 배열을 선언하고 입력받은 직사각형의 꼭짓점의 좌표들을 이용해 직사각형의 넓이만큼 이차원 배열에 저장해주었다. 이후 이차원 배열을 돌며 각 영역의 넓이를 구해 ans 배열에 넣어주었다. 풀이 - C++ #include #include #include using namespace std; int m, n, k, cnt; // m * n 크기 모눈..

[ 백준 ] 2485번 : 가로수 - ( C++ / C )

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이법 ( 알고리즘 ) 최대공약수를 이용한 문제이다. 가로수 사이의 간격을 구하고 그 값보다 큰 간격을 발견할 경우 최대공약수로 나누고 1을 뺀다. 풀이 - C++ #include #include using namespace std; int n; // n : 이미 심어져 있는 가로수의 수 int gcd(int a, int b) { if (b == 0) return a; return g..

[ 백준 ] 2660번 : 회장뽑기 ( C++/C )

문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 알고리즘 ( 풀이법 ) 플로이드-워셜 알고리즘이 무엇인지 몰라 인터넷에서 해설을 보고 풀었다. 각 간선의 가중치는 1이고 최소 비용을 저장한다. 이 중 가장 작은 최소 비용을 가진 회원들을 골라 출력한다. 학기 중이고 시험기간이라 여러 언어들로 문제풀이 하기 빠듯해 한동안 c++로만 문제를 풀듯하다. 풀이 - C++ #include #include using namespace std; int..