상위 99.99%의 PS

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으로 두고 시작해보자. 두 사람이 입력으로 주어..

www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net n>32일때는 비둘기집 원리에 따라서 0을 출력했고, n 32: print(0) else: for i in range(n): for j in range(n): for k in range(n): tmp = 0 if i == j or j == k or i == k: continue for x in range(4): if a[i][x] != a[j][x]: tmp += 1 if a[j][x] != a[k][x]: tmp += 1 if a[i][x] != a[k][x]: tmp += 1 ans = min(tmp,..

www.acmicpc.net/problem/20528 20528번: 끝말잇기 욱제는 준원이랑 끝말잇기를 하고 있다. 준원이가 시작하자마자 '스트론튬'을 외쳐서 욱제는 피가 거꾸로 솟았다~ 솟으면 백두산~ 백두산은 높아~ 높으면 비행기~ 비행기는 빨라~ 빠르면 기차~ www.acmicpc.net 어자피 주어진 문자열의 첫 글자와 마지막 글자는 같으니 주어진 문자열의 첫 글자를 세트에 집어넣었다. 1 2 3 4 5 6 7 n=int(input()) a = list(map(str,input().split())) q = set() for i in range(n): q.add(a[i][0]) print(1 if len(q) == 1 else 0) cs 오타, 오류 지적 환영합니다.

www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹 맨 윗줄은 2^10가지의 경우를 모두 테스트하고, 2번째 줄부터 그 위 전구가 켜져있으면 스위치를 누르는 방식으로 쭉 진행하면 된다. 그러고 마지막줄까지 진행한 후, 마지막줄에 켜져있는 전등이 있는지 확인하면 된다. 레퍼런스 당해서 힘들었다.. 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 3..

시간 제한이 1초이기 때문에 점프를 하는 모든 경우를 확인하는 것은 힘들 것 같다. 마지막 칸으로 갈 수 있는 모든 칸을 확인하여, 그 칸들 중 가장 왼쪽에 있는 것을 고르는 것을 반복하여 이 횟수를 세면 된다. 빨간색으로 칠해진 마지막 칸으로 갈 수 있는 칸은 초록색으로 칠한 8번째, 9번째 칸이다. 이 중 가장 왼쪽에 있는 8번째 칸을 기준으로 다시 확인하면, 5~7번째 칸을 통하여 8번째 칸으로 갈 수 있다. 이러한 과정을 반복하면, 이렇게 첫번째 칸까지 오게 되는데, 첫번째까지 왔다는 것은 첫 칸부터 끝까지 가는 방법이 존재한다는 것을 의미한다. 만약 빨간색 칸으로 올 수 있는 초록색 칸들이 존재하지 않는다면, -1을 출력하면 된다. 반복문으로 짤 방법이 떠오르지 않아서 재귀적으로 짰다. [소스코..

www.acmicpc.net/problem/17302 17302번: 흰색으로 만들기 첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 2,000) 다음 줄부터 N개의 줄에 걸쳐 각 행의 상태를 나타내는 길이 M의 문자열이 주어진다. 모든 문자열은 'B'와 'W'로 이루어져 있다. i 번째 줄, j 번째 문자 www.acmicpc.net 1~3번 행동의 차이를 보다가, 2번과 3번이 선택한 칸의 반전 여부가 다르다는 것을 알게 되었다. 모든 칸에 2번 행동을 취해준 후 결과에서 검은색이 있다면 그 칸은 3번 행동을 취해야 했던 칸임을 알 수 있다. 모두 3번 행동을 돌리고 흰색이 있으면 2번 행동을 취해야 했던 것이기도 하다. 어떻게 하던 상관은 없다. 1 2 3 4 5 6 7 8 9 10 11 12 1..

www.acmicpc.net/problem/19846 19846번: 신기한 연산 재현이는 문제를 풀다가 신기한 연산을 발견했다. 이 연산을 사용하면 홀수 번 등장하는 원소가 단 하나 있는 원소들의 나열에서 그 원소를 빠르게 찾을 수 있다. 예를 들어 수열 (1, 3, 2, 1, 2)에 www.acmicpc.net 입력을 잘 보면, 각 구간의 너비는 2N - 1 이상의 홀수이다. 따라서 aabbccddee.... 꼴로 만들면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 n,m,q=map(int,input().split()) ans = '' i = 96 while len(ans) != m: i += 1 if i == n + 97: i -= n ans += chr(i) if len(ans) =..

www.acmicpc.net/problem/20366 [사용한 알고리즘] 두 포인터 [시간복잡도] O(N^3) 먼저 i번째, j번째 눈덩이 두개를 정해서 눈사람1의 높이를 정해준다. 이를 기준으로 두번째 눈사람을 두 포인터를 이용하여 구할 수 있다. 더 빠른 방법이 있을 것 같지만 잘 모르겠다. n = int(input()) li = sorted(list(map(int, input().split()))) ans = 10**10 for i in range(n): for j in range(i+1, n): s1 = li[i] + li[j] # 눈사람1의 높이 a = i b = n-1 while True: # li[i], li[j]는 이미 사용한 눈덩이이므로 넘겨줘야 한다. while a == i or a =..