조용하지않는개발Blog

https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 토너먼트가 반씩 줄어든다는 생각을 가지고 풀면 해결되는문제 라운드의 개수를 미리 파악하고 전체 토너먼트 경기를 반씩 줄어가면서 찾는 방식을 택함 import sys input = sys.stdin.readline n, kim,im = map(int,input().split()) max_n=1 while True: if n

https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 전부다 if문으로 처리하면 되려나 했으나 리스트에 크로아티아 알파벳을 작성하고 변경해버리면 쉽게 풀리는 문제 # 크로아티아 알파벳 import sys croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] input = sys.stdin.readline n=input..

https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자 그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다. M이상도 있고, 소수가 없는 경우는 첫째 줄에 -1을 나오게 하는 것만 고려해서 풀면 된다. import sys input = sys.stdin.readline start=int(input(..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 모든 경우의 수를 다 확인하면서 S가 되는지 확인하는 함수를 만들어 풀면 될듯함 import sys input = sys.stdin.readline n, s = map(int, input().split()) s_list = list(map(int, input().split())) count = 0 def dfs(i,sum): ..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 -(마이너스)를 기준으로 split을 통해 나누었다. 나눈곳에 숫자만 존재하면 그대로 두고 +가 있으면 합치게 하였다. 첫번째 숫자는 result에 넣어놓고 2번째부터의 리스트는 빼주면 최소릐 값이 나온다. import sys input = sys.stdin.readline n = input() n = n.strip().split('-') n_list=[]..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 N*N의 그래프 형식으로 되어있는 문제 -> 리스트로 그래프를 만들어야한다. x,y형식의 for문 문제를 풀겠네 생각함 반복적으로 자르고, 개수 확인하는 형식이 재귀함수로 풀어야할듯함. -1,0,1의 수가 n*n의 수이면 결과가 1이라는 것으로 처리했고 아닌경우에는 재귀함수로 3을 나누어 다시 확인하는 형식으로 진행 import sys input = ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자 그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다. import sys input = sys.stdin.readline start, end = list(map(int,input().split())) n_list = [False,False]+[True]*(end-1..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자 그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다. import sys input = sys.stdin.readline while True: n = int(input()) if n==0: # 종료 시키기 break n_lis..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 연속된 몇개의 수를 더해서 큰 합을 구하는 문제이다. 입력을 통해 n이 최대 10만인것을 보아 n^2은 하면 안될것으로보인다. 그렇다면 dp(다이나믹 프로그래밍)문제일 것이라고 생각을하고 접근하였다. dp를 담을 리스트를 생성하고 임의의 수열에 처음부터 하나씩 비교하며 큰값을 dp에 작성하며 접근한다. 예제 문제를 통해 처음에 있는 10은 dp[0]에 10을 입력하고 이어..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보았을때 동전의 총 n종류가 있고 그 가치의 합이 k로 만드는 문제인데 이때 필요한 동전의 개수를 최소로 하는 문제이다. 또한 동전의 가치 a가 오름차순으로 되어있다고한다. 오름 차순으로 되어있따는 것은 큰 값을 먼저 확인하고 k안에 포함이 된다면 빼주면서 계산하면 최소의 개수를 찾을 수있다..