joseph0528 코딩 블로그

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 처음에 봤을 땐 그리디로 큰 값부터 작은 위치에 값을 더하는 방식으로 하고 싶지만 그러면 틀리게 된다. 이 문제는 dp 문제인데 i번째 블록을 움직일 수 있는 경우는 왼쪽 탑에 올린다, 오른쪽 탑에 올린다, 버린다 이렇게 3가지의 경우가 있다. 이때 왼쪽 탑과 오른쪽 탑으로 분리하지 말고 왼쪽 탑과 오른쪽 탑과의 높이 차로 dp 테이블을 만들 수 있다. 그럼 이렇게 정의하자 dp ..

아쉬우면서 괜찮은 결과인 거 같다. 3,4번 테케를 못 긁어서 200으로 끝났는데 그래도 1번이 dp인데 풀었다는 거와 못해도 동상은 받으니 처음 본선치곤 잘 본 거 같다는 생각이 든다(19만 원 3동 ㅋㅋㅋ) 처음에 1번을 풀다가 맞왜틀 했다가 한 가지 처리를 안 해줬다는 거를 알고 해 줬는데 그 조그마한 실수 때문에 10분 정도를 날렸고 2번은 생각은 쉬웠는데 구현이 잘 안돼서 3시간 이상을 날렸다 그다음 3번에서 조금만 긁고 4번을 갈려고 했는데 1점도 안 긁혀서 계속하다가 결국엔 200점으로 끝났다 1. 계산 로봇 위에서 말했던거처럼 dp다 어떤 점 (a, b)가 있을 때(y, x 순) |a-i|

solved.ac 티어 : 골 5 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp로 된다는걸 알면 쉬운데 dp인걸 알아채기가 어렵다고 해서 골 5라고 한다. 바로 문제풀이를 설명하자면 dp [i][j]=(i, j) 번째 점을 포함하는 정사각형의 한 변의 최대 길이 이게 끝이다. dp [i][j]를 구하려면 (i, j) 번째 점이 0일 때는 0이고 1일 때는 (i-1, j)==(i, j-1)==(i-1, j-1) 이면 셋 중 하나의 값+1이 dp [i][j]가 되고 아닐 떼 셋 중 가장 작은값+1을 해주면 된다..

solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..

solved.ac 티어 : 골 4 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 오랜만에 시험 끝나고 돌아왔다 당연히 시험은 망했고 오랜만에 와서 풀이를 쓸려고 한다 이 문제는 KOI 2013 중등, 고등 1번 문제이다 이 문제는 자명 풀이가 이분 탐색(binary search)이라는데 그것보다 스위핑처럼 하는 방법이 먼저 떠올라 그걸로 풀었다 방법은 이분 탐색만큼 간단한데 동물들의 점..

solved.ac 티어 : 플래 5 www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 모든 간선을 이어주고 가중치는 로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다. import sys sys.setrecursionlimit(10**9) m=int(input()) e=[] def find(a): if uf[a]

solved.ac : 골드 3 각 점들마다 ccw를 구해서 교차했는지 안 했는지 판별하면 된다. 한 선분의 두점과 다른 선분의 점과 ccw를 했을 때 1,-1 또는 -1,1 또는 0,0 이면 교차한다. 반대도 해주면 된다. def q(x1,y1,x2,y2,x3,y3): r=x1*y2+x2*y3+x3*y1;r=r-y1*x2-y2*x3-y3*x1 if r>0:return 1 elif r