본문 바로가기
728x90

알고리즘316

[python] 백준 2841 외계인의 기타 연주 https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 문제 해결 n과 p가 매우 크기 때문에 dp를 사용하기는 부담스럽다. (dp는 주어진 숫자보다 큰 것을 모두 봐야하기 때문) 따라서 stack을 1~6번 스택을 만들고 FIFO 방식으로 들어가거나 나간 횟수 계산을 하는 것이 편하다. CODE import sys input = sys.stdin.readline n, p = map(int, input().spl.. 2023. 3. 15.
[python] 백준 1969 DNA https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 문제해결 각 자리의 알파벳을 보고 가장 많은 알파벳이 Hamming Distance이 가장 작은 DNA가 된다는 것은 쉽게 알 수 있다. 따라서 각 자리별로 가장 많은 알파벳과 그 알파벳이 아닌 것들의 개수 합을 구하면 된다. CODE n, m = map(int, input().split()) graph = [list(str(input().rstrip(.. 2023. 3. 15.
[python] 백준 5557 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 해결 이전 항들의 영향을 받는다. 이전 항들까지 더하기, 빼기를 이용해서 만들 수 있는 것은 0이상 20 이하여야 한다. dp로 가지수를 만들수 있다. dp[i][j]를 j-1번째 항까지 더하기 빼기를 이용해서 i를 만들 수 있는 가지수를 나타낸다. dp[A[n-1]][n-2] 의 값을 구하면 된다. CODE import sys input = sys.stdin.readline n = .. 2023. 3. 15.
[python] 백준 17626 Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해결 n보다 작은 수의 제곱수의 개수를 연결하는 것이므로 dp를 이용하는 것이 좋겠다는 생각을 하게 된다. 시간제한이 0.5초이기 때문에 빡세다. (python3로는 계속 탈락... pypy3로 풀었는데 python3까지 최적화를 못시키겠다.) 1 = $1^{2}$ 이므로 dp[1] = 1 dp[0] = 0으로 고정한다. 2부터는 for문을 통해 알아갈 것.. 2023. 3. 14.
728x90