뇌 채우기 공간

문제 k원을 만드는데 필요한 동전 개수의 최솟값을 출력하라 문제 풀이 입력받은 코인을 배열에 저장하고 내림차순으로 정렬한다. k원보다 코인이 큰 것은 지나가고 k원보다 작아지면 k원을 coin으로 나눌 수 있는 지 확인한다 나눌 수 있으면 몫이 coin의 개수이고 나머지가 남으면 나머지를 다음으로 작은 코인으로 나눈 것을 더하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys kind_of_coin, money = map(int,sys.stdin.readline().split()) coins = [] for _ in range(kind_of_coin): coin = int(sys.stdin.readline()) coins.append(coin) coins.rev..

문제 주어진 식에 괄호를 적절히 쳐서 식의 값을 최소로 만들어라 문제 풀이 처음에 55-50+40을 보고 그냥 +를 다 마이너스로 바꾸면 되지 않을까라고 생각했다. 그런데 55+50+40-30+20+10 이면 40 뒤에부터 -로 바꿔야하기 때문에 일단 -를 기준으로 입력값을 split하여 배열에 넣는다. 그리고 첫번째로 들어가 있는 값에서 그 뒤의 모든 값을 빼준다 코드 # ------------------------------ arr = input().split('-') # print(arr) result = 0 for i in arr[0].split('+'): result += int(i) for i in arr[1:]: for j in i.split('+'): result -= int(j) prin..

문제 피보나치 함수를 구할때 0과 1이 몇 번 호출되는지 구하여라 문제 풀이 fn_2 에 fibonacci(n-2)의 0의 개수와 1의 개수를 저장한다. fn_1에 fibonacci(n-1)의 0의 개수와 1의 개수를 저장한다. fn에 fibonacci(n)의 0의 개수와 1의 개수를 저장한다. fn의 0의 개수는 fn_1의 0의 개수와 fn_2의 0의 개수를 더한 것이다. fn의 1의 개수는 fn_1의 1의 개수와 fn_2의 1의 개수를 더한 것이다. fn에 저장해주고 나서 fn_1에 있던 값을 fn_2로 옮기고 fn에 있던 값을 fn_1로 옮긴다. 코드 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 num = int(input()..

백준 문제 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합이다. 어떤 자연수 M의 분해합이 N인 경우 M을 N을 생성자라고 한다. 자연수 N이 주어졌을때 N의 가장 작은 생성자를 구해라 문제풀이 주어진 숫자까지 1부터 분해합을 구한다. 중간에 분해합이 주어진 숫자와 같아지는 순간 break하고 출력한다. 중간에 break될 경우 check를 False에서 True로 바꾼다 check가 False로 끝까지 남았을 경우 주어진 숫자의 생성자가 없다는 뜻이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 num = int(input()) check = False for i in range(1,num+1): generated = 0 splits= [] for j in ..

백준 문제 카드 3장을 뽑아 M을 넘지 않으면서 M에 최대한 가까운 합을 만들어라 문제 풀이 한개씩 카드를 뽑아서 합이 M보다 크면 넘어가고 M과 같거나 같으면 그 합이 가장 큰 것을 result에 담아서 출력한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N,M = map(int, input().split()) numbers=list(map(int, input().split())) # print(numbers) result = 0 for i in range(N): for j in range(i+1, N): for k in range(j+1, N): if numbers[i] + numbers[j] + numbers[k] >M: continue else: result = max(re..

문제 조규현의 좌표 (x1, y1)과 백승환의 좌표(x2,y2)가 주어지고 조규현과 류재명의 거리 r1, 백승환과 류재명의 거리 r2가 주어진다. 류재명이 있을 수 있는 좌표의수를 출력하라 문제 풀이 조규현의 좌표를 중심으로 r1을 반지름으로 하는 원의 테두리의 모든 좌표가 류재명이 있을 수 있는 거리이다 백승환의 좌표를 중심으로 r2를 반지름으로 하는 원의 테두리의 모든 좌표가 류재명이 있을 수 있는 거리이다. 이때 두 원이 한 점에서 접하면 류재명이 있을 수 있는 좌표는 1개이다. 두 원이 두점에서 접하면 류재명이 있을 수 있는 좌표는 2개이다. 두 원이 접하지 않으면 류재명이 있을 수 있는 좌표는 0개이다. 두 원이 일치하면 류재명이 있을 수 있는 좌표는 무한개이다. 코드 1 2 3 4 5 6 7 ..

문제 계단은 한번에 한 계단 or 두 계단씩 오를 수 있다. 연속 세개를 밟으면 안된다. 마지막 도착 계단은 반드시 밟아야한다. 이때 얻을 수 있는 점수의 최댓값을 구해라 문제 풀이 계단이 1개일때는 1개만 밟을 수 있다 계단이 두개일때는 두개 다 밟을 수 있다. 계단 세개일때는 마지막 계단은 꼭 밟아야하니, 첫번째 계단과 두번째 계단 중에서 점수가 높은 것을 밟을 수 있다. 계단이 네개 이상일때는 그 전 계단을 밟은 게 점수가 큰지, 전 계단을 안밟은게 점수가 큰지 확인한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys step_total = int(input()) steps = [] for _ in range(step_tot..

백준 문제 N*N 체스판에 퀸 N개를 놓는다 퀸의 좌우상하 대각선에 다른 퀸이 없어야한다. 그렇게 N개를 놓는 경우의 수를 출력하라 문제 풀이 맨 위에 줄 1번째 칸부터 확인한다 두번째 줄에 되는 칸이 있으면 세번째 줄로 내려간다 세번째 줄에 되는 칸이 없다 그럼 다시 두번째 줄로 올라간다 두번째 줄로 올라가서 다음칸을 확인한다 세번째 줄로 가서 되는 칸이 있는지 확인한다 네번째 줄로 가서 되는 칸이 있는지 확인한다 없다 그럼 1번째 줄 두번째 칸으로 올라간다 1번째 줄 두번째 칸을 확인한다 두번째 줄에서 되는 칸이 있는지 확인한다 세번째 줄에 되는 칸이 있는지 확인한다 네번쨰 칸에 되는 칸이 있는지 확인한다 있으면 횟수를 하나 올린다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

백준 문제 1~N까지 자연수 중에서 중복없이 M개를 고른 수열 고른 수열은 오름차순이어야한다. 문제 풀이 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 어떤 노드의 유망성 점검 후 , 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색 1부터 시작해서 그 숫자와 다음 숫자를 배열에 넣고 , 배열의 길이가 m이 되면 print하고 맨 뒤의 숫자를 pop한다. 그 다음 숫자를 배열에 넣고 배열의 길이가 m이 되면 print하고 맨 뒤의 숫자를 pop한다 ... 코드 n,m = list(map(int,input().split())) #1234 2 s = [] def dfs(start): #start..

문제 정사각형 색종이 한 칸에 1이나 0으로 모두 채워져있지 않으면 4등분 한다 문제 풀이 처음 입력 받은 값을 color_paper에 2차원 리스트로 저장한다. 맨 처음 [0][0] 원소를 check라고 두고 색종이를 다 돌면서 check와 같지 않은 부분이 있는 지 확인한다. 같지 않은 원소가 나타난 즉시 4등분한다 if문에 안걸리고 4등분을 안하게 되면 그 check가 1인지 0인지 확인하고 white와 blue에 맞게 +1을 한다. 코드 import sys n=int(sys.stdin.readline()) color_paper=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]#x행 y열 white=0#0이면 흰생 blue=0#1이면 ..