joseph0528 코딩 블로그

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 간단한 mst문제이다. 점의 y, x가 주어지고 정점 개수-1개의 간선을 이어야 되니 모든 점을 이어준다. 이때 가중치는 두 점의 거리가 된다. 그러므로 두 점의 x좌표의 차 제곱 + 두 점의 y좌표 차 제곱을 루트 해준 값이 두 점 사이의 거리가 된다. import sys,math sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 이문제는 기본 mst(최소 스패닝 트리)에서 간선을 추가할 때 두 점이 다른 점이라면 추가하는 방식으로 하면 된다. 그리고 마지막에 -1 처리를 해주면 된다. import sys sys.setrecursionlimit(10**9) def find(a): if uf[a]

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 티어 : 플래 3 www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 이문제는 수열과 쿼리 6을 응용하면 된다. 6 코드에서 값을 재일 마지막에 구해주면 된다. 처음에는 안될 줄 알았는데 이렇게 해줘도 시간이 여유롭게 남는다. void add(int u){ cn[cnt[u]]--; cn[cnt[u]+1]++; } void ms(int u){ cn[cnt[u]]--; cn[cnt[u]-1]++; } fcnt=0..

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이문제는 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 나올 수 있는 최대 개수를 구하는 것이다. 이때 이문제에서 꼬이지 않게 하려면 i번째의 값보다 i+1번째 값이 더 커야 된다. 즉 이문제는 LIS(최장 증가 부분 수열)이라는 거다. 그러므로 이분탐색 LIS를 구해주면 된다. import sys sys.setrecursionlimit(10000..

solved.ac 티어 : 플래 4 www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제도 보자마자 버거운 버거라 응요이라는 거를 알 수 있다 그렇기 때문에 이것도 버거운 버거를 풀면 날먹이다. 이문제는 변경이 없는 대신 올바른 괄호 문자열인지 확인하는 것이 입력으로 주어진다. 그러므로 변경 부분을 지우고 입력을 받은 값을 구간에 넣어주면 끝이다. #include #include using namespace std; typedef long lo..

solved.ac 티어 : 플래 2 www.acmicpc.net/problem/17407 17407번: 괄호 문자열과 쿼리 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다. 버거운 버거를 풀고 오면 거저로 얻는 문제이다. 버거운 버거:joseph0528.tistory.com/8 BOJ 19851(버거운 버거)풀이 세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무..

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

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 이문제는 dp이다. 점화식은 dp[n-1][l-1][r]+dp[n-1][l][r-1]+(i-2)*dp[n-1][l][r]이다. dp[n-1][l-1][r]는 재일 왼쪽 막대를 뺐을 때이고 dp[n-1][l][r-1]는 재일 오른쪽 막대를 뺐을 때이고 dp[n-1][l][r]*(i-2)는 양쪽 막대를 제외한 나머지 막대를 배치할 수 있는 경우의 수이다. import ..