yoo.dev

문제 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 풀이 항상 n * m 형태의 2d 어레이를 만들고 시작하는데, 이번에는 그럴필요 없을것 같아서 절취선만 가로 세로 나눠서 받은 후, 이중 포문으로 브루트포싱 해줬다. import sys C, R = map(int, sys.stdin.readline().split(" ")) N = int(sys.stdin.readline()) li_c = [0, C] li_r = [0, R] for _ in range(N): dir, num = map(int, sys.stdin...

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 소수 찾기(yuuj.tistory.com/158) + 투포인터 알고리즘(yuuj.tistory.com/160)인 문제. 최소 소수는 2이기 때문에 인풋으로 1이 들어올 경우를 예외처리 안해주면 런타임에러가 난다. import sys # n까지의 소수 리턴 def prime(n): li = [False, False] + [True for _ in range(n-1)] p = [] for i in range(len(li)): if li[i]: p.append(i) for k in range(i+i, len(li), i): li[k] = False return p S = in..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 2003번(yuuj.tistory.com/160)과 비슷하게 투포인터 알고리즘으로 풀면 되는데, 주의해야할 점은 1. 합이 S와 일치하는 경우가 아닌, S이상일 경우이라는점 2. 가능하지 않을 경우엔 0을 리턴해야한다는점이다. 문제 제대로 읽기 !!!!! import sys N, S = map(int, sys.stdin.readline().split(" ")) arr = list(map(int, sys.stdin.readline().sp..

문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 투포인터 알고리즘을 이용해서 풀었다. 배열의 인덱스를 start, end 두 변수에 저장해서 원하는 합보다 sum(arr[start:end])가 작아질 경우엔 end를 하나 증가시키고, 같거나 클 경우엔 start를 하나 증가시킨다. 주의할점은 루프를 끝내는 시점이다. end가 배열의 길이가 되었을때 루프를 멈춰줬더니, start가 이동하면서 하나씩 빼주는 부분이 생략되어 틀린 답이 나왔다. 또 arr[star..

문제 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 풀이 파이썬으로 제출한 사람들은 다 밀러-라빈 소수판별법을 사용했지만 나는 다른 방법으로 풀고싶어서 고집을 부리다가.. 결국 시간초과가 나서 pypy3로 제출한 문제. 두 끈의 합 s가 2 or 3일 경우 -> NO 4 이상의 짝수인 경우 -> YES 그리고 그 외에는 홀수인 경우만 남는다. 홀수는 홀수+짝수로밖에 이루어질 수 없고, 짝수인 소수는 2밖에 없기 때문에 홀수가 두 소수의 합이 되려면 2 + 홀수소수 인 경우밖에 없다. 따라서 s-2가 소수인지 확인..

문제 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 에라테스토스트의 체를 활용해서 최대값인 1000000까지의 소수 여부 모두 구하고, 그 후에 무한루프를 통해서 0이 들어오기 전의 값들에 대해 판별을 해주면 된다. 판별하는 방법은 가장 작은 소수(a)부터 하나씩 n-a도 소수인지 확인을 하면 되는데, list에서 in을 사용할 경우 시간복잡도가 O(n) 이 되기 때문에 따로 소수 리스트를 만들지 않고, arr을 그대로 사용해서 소수인지 아닌지 확인하는 시간을 O(1)으로 줄였다..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 에라토스테네스의 체(yuuj.tistory.com/156)를 이용해서 풀 수 있는 문제. import sys def primelist(n): arr = [True for _ in range(n+1)] for i in range(2, (int(len(arr)**0.5)+1)): if arr[i]: for k in range(i+i, len(arr), i): arr[k] = False return arr m, n = map(int, sys.stdin.readline().split(" "..

문제 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 풀이 엄청 간단한 문제지만 같은수일경우 작은수부터 출력해야하는 정렬 조건과, 카드의 최대값을 제대로 안읽어서 20분동안 삽질한 문제 만약 진짜 코딩테스트였다면 어이없게 20분을 날릴뻔했다. 문제 꼼꼼히 읽는 습관을 기르자!! import sys from collections import Counter N = int(sys.stdin.readline()) arr = [] for _ in range(N): arr.append(int(sys.stdin.rea..