PS공부하기 싫어서 쉬워보이는 문제로 아무거나 골라 풀었다. 의외로 재미있어서 좋았다. https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 아이디어는 역시 간단하다. 한 건물을 중심으로 다른 두 방향으로 쭉 뻗어나가면서 gradient를 계산해 주면 된다. 예를 들어 다음과 같은 입력에서 5번째 건물을 보자. 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 5번째 건물의 높이는 6이다. 어느쪽 방향이든 첫 번째 건물을 무조건 볼 수 있다..

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 그다지 어렵지는 않은 DP 문제이다. 다만 한 가지 아이디어가 중요한데, 마름모가 네 변으로 구성되므로 그 네 변의 길이를 brute-force로 구하지 말고 memorization을 사용해서 구하겠다는 아이디어만 내놓으면 된다. 나는 먼저 UpRight방향, UpLeft방향, DownRight방향, DownLeft방향에 대해서 그 map을 마지막으로 하는 가장 긴 연속적인 1의 길이를 DP table에 저장하였다. 이 과정에서는 directi..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 오랜만에 그래프 문제를 풀었다. STL도 한동안 사용하지 않다가 사용하려니 실수가 많았다. 이 문제는 원래는 위상정렬이랑 DP 문제라는데, 위상 정렬로 풀기가 조금 애매해서 위상정렬 비스무리한 무언가로 풀게 되었다. 해결 방법은 이렇다. 맨 처음에 queue에(나는 그냥 vector를 사용했다) 처음부터 시작할 수 있는 건물들을 의 pair로 집어넣는다. 그 다음 각 iteration에서 q..

아주 멋진 닭 내가 그와 눈을 마주쳤을 때, 그는 나에게 다가왔다. 오, 아주 멋진 닭이여! '꼬끼오' 하고 울어다오. 직접 쓴 시이다.

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net divide and conquer 문제인데, 다소 까다로운 부분이 있다. 직접 2차원 배열을 돌면서 수를 일일이 입력하고 다니면 N>=15라는 조건 때문에 시간 초과가 발생한다. 따라서 4개의 사분면으로 분할하여 계산을 생략해주는 과정이 반드시 필요하다. 나는 sizeRec에 미리 작은 사분면의 넓이를 저장한 후에 어느쪽 사분면이냐에 따라서 0, 1, 2, 3을 곱해 주어 직접 계산하는 과..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net divide and conquer로 해결할 수 있는 문제이다. start에서 end까지의 부분 히스토그램을 보았을 때, 그 안에서 만들 수 있는 직사각형의 최대 넓이는 세 경우 중 하나에서 구할 수 있다. 편의상 mid = (start+end)/2 로 정의한다. 1. start ~ mid까지의 부분 히스토그램 중 최대 넓이 2. mid+1 ~ end까지의 부분 히스토그..