상위 99.99%의 PS

www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족 www.acmicpc.net CHT 기초문제이다. 아래 자료를 먼저 읽고 온다면 도움이 된다. stonejjun.tistory.com/50 m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221418495037&proxyReferer=https:%2F%2Fwww.goog..

www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 단순 구현문제다. 거북이가 간 점들의 최대, 최소가 되는 x좌표와 y좌표로 직사각형의 넓이를 구할 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import sys input = sys.stdin.readline t = int(input()) def fr(): k[0] = min(no..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 중앙값을 기준으로 우선순위 큐 두 개를 만들어주고 풀었다. 코드 더러워지는거 싫어서 hpp = heapq.heappop hps = heapq.heappush 라고 미리 써두고 풀었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import heapq, sys input = sys.stdin.readline hpp..

https://www.acmicpc.net/problem/3344 3344번: N-Queen 첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다. www.acmicpc.net www.acmicpc.net/problem/21133 21133번: N-Queen 2 N개의 줄을 출력해야 한다. i번째 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다. www.acmicpc.net 왜 또 constructive지? 3344랑 코드는 같다. 6k+2, 6k+3에서 안되는거 알고 찾다가 도저히 모르겠어서 위키에서 찾고 그대로 구현했는데.. 좀 그렇다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

맞은건 ABC이다 A 가장자리부터 k번, 맨 앞쪽과 맨 뒤쪽의 글자가 같은지 확인했고, k=0이면 1, n=2k면 0을 출력하는 조건을 달아주었다. B 012345...n 이런 배열이면 n+k를 출력했고, 아니라면 멀티셋 S에 추가되는 수는 계속 같으므로 입력으로 들어온 배열을 set으로 입력받아서 거기에 추가될 수를 집어넣고, 그 길이를 출력했다. C 절댓값을 기준으로 광부 배열과 다이아몬드 배열을 각각 정렬 후, 둘이 거리를 구해주면 된다. D 조건 잘못봐서 틀리다가 뇌절하고 시스텟 마지막테케에서 틀림. 봉우리 구하고 조건이 뭐가 많은데 모르겠다. 나중에 다시풀어야지 E 3k-2열마다 색칠하고 아무거나 잡고 이어주면 된다. D에서 시간 다쓰고 못풀었다.

www.acmicpc.net/problem/20913 20913번: Mixtape Management Output $n$ distinct integers in lexicographically increasing order, your sequence of filenames. All numbers must be positive integers less than $10^{1000}$ and may not contain leading zeroes. Any valid sequence of filenames will be accepted. www.acmicpc.net 이런 구성적은 재밌어서 좋다 노트에 조금 끄적이다 보면 두 개의 숫자만으로도 풀수있다는 사실을 금방 알 수 있다. 나는 1과 2로 풀었다. n번째 단..

cp에 한없이 약해서 (그리고 귀찮아서) b번까지만 풀어왔는데, 이젠 C번까지 풀어야될것같다.. 능지 올려야됨 A: a,b,y,z 이 4개만으로 풀린다 B: 몬스터의 공격력이 작은 것 부터 잡으면 된다. C: 나는 삼분탐색으로 풀었다. 그러나... 시스텟에서 틀렸다. 왜 틀렸나 했더니 n이 1, 2일때 범위 밖의 수를 물어보고 있더라.. 범위 제발 잘 보자... 그리고 n=1이나 2일 때의 테케가 없었다는게.... 블루 갈수 있었는데 한번 더 해야 올라가게생겼다 수정) 그냥 삼분탐색이 안된다. 멍청했다,, 이분탐색 하면 되는거였다. 그리고 요즘 수능 준비때문에 바빠서 ps를 위한 시간이 많이 부족하다..

www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net [DFS를 이용한 내 풀이] 1번 정점부터 dfs를 돌며 방문하지 않은 정점에 대해 팀의 색을 돌아가면서 입혀주었다. 그 후, 모든 간선에 대해 두 정점의 색이 같은지 확인해주었다. 파이썬으로 하니까 터져서 c++로 풀었다. [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net 개꿀잼 애드혹이다 길이가 1인 수열은 무조건 증가하는 팰린드롬 수열이다. 문자열의 중심을 잡고, 그 중심을 기준으로 바깥쪽으로 한 칸씩 이동하여 두 수가 같은지와, 증가하는 팰린드롬 수열인지를 확인하면 된다. 문자열의 길이가 짝수일 때와 홀수일 때를 나누어 풀었다. 1 2 3 4 5 6 7 8 9 1..

www.acmicpc.net/problem/20531 20531번: 인간관계 S인터넷고등학교에는 $N$명의 학생이 있다. 이들 사이에 몇몇은 서로 친구 관계를 맺고 있다. 친구 관계는 다음 세 가지 조건을 만족한다. 모든 학생은 자기 자신의 친구이다. 학생 $x$가 학생 $y$ www.acmicpc.net 벨 수를 알고있으면 좋다. union find를 활용한 dp문제이다. 차근차근 풀어보자 1. 점화식 dp[i][j] = (i개의 그룹을 j개로 묶는 경우의 수) 라고 하면, dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] 라고 점화식을 세울 수 있다. 나는 미리 dp 배열을 채워두고 시작했다. 2. 그룹의 수 세기 그룹의 개수를 n으로 두고 시작해보자. 두 사람이 입력으로 주어..