PS
BOJ 1082 - 방번호
www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 예를 들어, N=4이면, 문방구에서 파는 www.acmicpc.net 문제를 푸는 전반적인 아이디어는 이렇다 먼저 주어진 숫자에서, 첫번째 인덱스에서 부터 마지막번째 인덱스까지 가장 작은 수 first 두번째 인덱스에서 부터 마지막번째 인덱스까지 가장 작은 수 second 를 잡는다. 이 두 숫자를 잡아야 하는 이유는, 첫번째로, 가능한 비용범위 내에서 최저값을 잡아내기 위함이다 (문자열로 일정한 틀을 잡아줘야 최댓값으로 갱신이 가능하기 때문임, 물론 이는 구현 방법에 따..
BOJ 1022 - 소용돌이 출력
www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 구현 문제이다. 먼저 맵을 표현하는 배열 int adj[50][5] 를 선언한다. 주의할것은, 문제에서 (0, 0) 의 좌표가 (-3, -3) 이 들어가기 때문에, (0, 0) 을 그대로 적용시키면 틀리게 된다 그러므로, 좌표 맞출때만 신경써서 처리하면된다 그리고 입력 받은 값의 절댓값중 최댓값을 찾아서 그 값만큼 돌아야한다 (소용돌이의 최대갯수임) 그리고 나머지 4방향으로 돌아야 하는데, 소용돌이가 돌아가는 모양새를 보면 얼마만큼 움직여야 하는지 알 수 있게 된다 (그 값을 cnt 를 기준으로 처리) 그리고 4방향으로 돌면서 무..
BOJ 16120 - PPAP
www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 이 문제에서는 P 의 갯수를 세면서, 몇가지 조건을 통과하도록 작성하면 된다 먼저 입력받은 문자열을 쭉 돌면서, 현재 인덱스의 값이 P 이면 갯수를 하나씩 늘린다 그리고 앞의 문자가 P 가 두번 나왔으면서 동시에 다음 문자가 P 인 경우 PPAP 에 해당하므로 이 PPAP 를 P 로 치환한다. (앞에 이미 2개를 셌으므로 갯수 하나 감소) 그리고 다 탐색이 끝난 다음 마지막 P 의 갯수가 한개 남았으면, PPAP 에서 마지막 P 라는 의미이므로, PPAP 를 출..
BOJ 2515 - 전시장
www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1> N >> S; for (int i = 1; i > arr[i].first >> arr[i].second; sort(arr + 1, arr + N + 1); for (int i = 1; i
BOJ 3197 - 백조의 호수
www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 이 문제는 두가지 방식으로 풀 수 있다. 하나는 BFS 를 두 번 사용해서 푸는 방법과 또 다른 하나는 Disjoint-Set 과 BFS 를 섞어서 푸는 방식이 있다. 나는 BFS 를 두번쓰는 방식으로 처리하였다. 먼저 입력 받을때, 백조의 좌표를 따로 저장하고 (vector swan), 물의 좌표를 저장한다 (queue water_queue) 물의 좌표를 저장하는 이유는 하루씩 지..
BOJ 1450 - 냅색문제
www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 meat in the middle 이라는 알고리즘을 써서 풀어야 하는 문제이다 (참조) meat in the middle blog.naver.com/PostView.nhn?blogId=kks227&logNo=221382873753&proxyReferer=https:%2F%2Fwww.google.com%2F 밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25) 안녕하세..
BOJ 1826 - 연료 채우기
www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 이 문제는 그리디 방식으로 풀어야 하는문제다 왜냐면, 가지고 있는 연료의 양이 제한적이고, 주유소를 최소한으로 방문해야 하기 때문이다. 정렬의 기준은 현 위치에서 주유소 까지의 거리가 가까운 순서대로 정렬한다 그리고 목적지 까지의 거리(L) 와 현재 보유하고 있는 연료량(P) 을 비교했을때, P 가 더 적은 경우 주유소를 방문해서 충전을 해야만한다. 그리고 우선순위 큐(최대..
BOJ 1202 - 보석 도둑
www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 백준 1781 컵라면 (www.acmicpc.net/problem/1781) 문제와 코드 구조가 거의 비슷하다. 그리디와 우선순위 큐를 이용해서 풀어야 하는 문제 유형이다. 이 문제를 보고, 보석 가격이 비싼 순서대로 정렬하고, 가방이 무게 제한이 낮은 순으로 정렬해서 하나하나 비교해도 되지 않나라고 생각할 수 있지만, N 과 K 의 최대값..