HwangHub

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net algorithm_type math(정수론, 유클리드 호제법) is_clear False 문제 풀이 이 문제는 정말 "수학적인 사고"를 요하는 문제였다. 주어지는 숫자들은 모두 같은 숫자로 나눠서 같은 나머지를 가져야 하므로, 각 숫자들은 동일한 나머지 값을 뺀 상태에서 공약수가 존재한다는 의미이다. 따라서, 우리는 저 m이 어떤 수인지 알아내면 된다. 그러면 우리가 고등학교 때 x를 구했던 것 처럼, m을 구하..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수를 구할 때, 그 정의에 따라 우리는 아래 식을 쉽게 떠올릴 수 있다. def is_prime(n): for i in range(2,n): if n % i == 0: return False return True trash = input() li = list(map(int, input().split())) ans = 0 for i in li: if i == 1: pass elif is_prime(i): ans += 1 prin..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해석 위 문제는 조합으로도 쉽게 풀 수 있는 문제이지만, 백트래킹으로도 풀 수 있을 것 같아 백트래킹으로 풀어보려고 한다. 조합 이 풀이는 itertools 라이브러리의 조합을 이용하면 된다. 단순히 주어진 리스트 값에서 6개의 숫자를 뽑아주면 되는 문제다. 입력의 수가 주어지지 않아 혹시 몰라서 EOF처럼 try/except를 걸어주었다. # 첫 번째 풀이 : 조합 이용 impo..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/25916 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 첫 번째 풀이 우선, 조건에 따라 '연속'된 구멍의 '합'이 햄스터의 부피보다 작아야 하므로 투포인터로 풀면 되겠다고 판단했다. 이제 로직을 구성하면 되는데, 일정 연산 결과가 조건보다 작으면 냅다 오른쪽 포인터를 진행시키는게 일반적이라 생각했는데, 이번 문제에서는 포인터가 가리키는 범위의 합이 항상 햄스터의 부피 이하여야 하므로 오른쪽 포인터를 진행한 상황에서의 값이 몇인지 체크하고, 부피 이하로 들어올 경우 오른쪽 포인터를 진행시킨 뒤에 max 값(이후 결과값)을 저장했다. 이를 ..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 첫 번째 시도 1개만 제외하고 회문이 되는 경우를 유사 회문이라고 정의할 때, 그 문제가 되는 문자를 찾아서 저장해두고 투포인터로 문자열을 순회하면서 문제가 발생했을 때 사전에 저장한 문제의 문자와 비교하면 되겠다고 가정한 채 구성한 로직이었다. 결과는 실패였다. 가정은 그럴싸하였다고 생각했으나, 문제가 되는 문자를 찾는 로직에 오류가 있어서 제대로 문자를 찾아내지 못헀고, 이는 결국 실패로 이어졌다. import sys fr..

https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 문제 해석 다이나믹 프로그래밍은 분할 정복의 한 종류로, 복잡한 문제를 작은 문제들로 쪼개어 풀어내는 알고리즘이다. 여기서 핵심은, 잘게 쪼개진 문제 하나하나는 한 번만 푼다는 점이다. 다이나믹 프로그래밍을 적용시키기 위해서는 다음 두 가지 조건을 만족해야 한다. 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 조건 2. 작은 문제에서 구한 정답을 큰 문제에 적용할 수 있다. 해당 문제에서는 타일을 연속적으로 배치한 길이가 0, 1, 2와 같이 계속 쌓다가 어느 순간 길이가..

https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net RESULT """pypy3""" from collections import defaultdict import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) li = sorted(list(map(int, input().split()))) ans = 0 dd = defaultdi..

보호되어 있는 글입니다.