백준 파이썬 코딩 (50) 썸네일형 리스트형 백준 14888 연산자 끼워넣기 파이썬 https://www.acmicpc.net/problem/14888 백준 14888번: 연산자 끼워넣기 바로가기재밌는 백트레킹 문제이다2년만에 코딩하는건데 여전히 재밌는 것 같다.여기서 포인트는 하나만 잘 만들면 밑에는 똑같이 만들면 된다.마지막으로 주의할점은 나눗셈할때 음수인 경우이다 문제 설명에 맞게 코딩해주면 된다~import sys#최대 최소def back(i,k,t):#(index, 그 전 연산 값, 기호쓴것들 표시) global maxs, mins #지역 함수 밖에 있는 걸 수정할거니까~ if i == n:#맨 끝 index에 도착했으니 더이상 연산할게 없음 mins = min(mins,k) maxs = max(maxs,k) for j in rang.. 백준 28357 사탕 나눠주기 파이썬 https://www.acmicpc.net/problem/28357 28357번: 사탕 나눠주기 소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 $X$를 정한 뒤 최종 점수가 $X$점을 넘는 학생들에게 점수가 높은 www.acmicpc.net 간단한 이분탐색 문제였습니다. 최솟값과 최댓값 설정만 잘해주면 쉽게 풀릴것 같습니다. def ch(x):#나눠줘야하는 사탕 개수 체크 함 re = 0 for i in s: if i>x: re+=(i-x) return re n,m = map(int,input().split()) s = list(map(int,input().split())) a,b = 0,max(s)#점수의 최대값이 기준점의 .. 백준 16567 바이너리 왕국 파이썬 반례 O https://www.acmicpc.net/problem/16567 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net flip 횟수를 0이 나올때마다 구하면 시간초과가 나올 수 밖에 없는 문제이다. 0 > 1 로 바꿔줄때 flip 횟수를 구해야 시간초과를 피할 수 있다! 밑에는 반례입니다. 코드 설명은 아래에 하겠습니다. 입력 5 9 0 1 0 0 0 0 1 1 0 1 3 0 1 5 0 1 2 0 답 1 1 1 2 2 오답 0 0 0 1 1 핵심 포인트 정리입니다. 1. 양 옆이 .. 백준 28215 대피소 파이썬 https://www.acmicpc.net/problem/28215 28215번: 대피소 $2$차원 평면의 KOI 마을에 $N$개의 집이 있다. 각 $i$번째 집의 위치는 $(X_i , Y_i)$이다. $i$번째 집과 $j$번째 집 사이의 거리는 $|X_i - X_j | + |Y_i - Y_j |$이다. 즉, 두 집 사이의 거리는 $X$의 차이와 $Y$의 www.acmicpc.net 문제에서 최대 K개의 대피소를 설치할 수 있고 거리가 최소가 될 때 최대값을 구하라고 했으니 백트레킹을 사용하면 모든 경우의 수를 탐색할 수 있어 문제를 풀 수 있을 것이라 생각했다. 그래서 처음에는 문제를 풀기위해 아래와 같이 코딩했었다. import sys def ch(w):#대피소의 개수에 따라 최솟값을 구하는 알고리즘.. 백준 25917 Prime Arrangement 파이썬 증명 X https://www.acmicpc.net/problem/25917 문제에서 소수만 주어진 이유는 서로 다른 소수 * 소수는 값이 안 겹치기 때문이다. 여기서 알 수 있는것은 문제의 답은 나올 수 있는 모든 조합의 경우의 수인것이다. (P는 고려할 필요가 없음. 조합을 만들고 알맞게 순서를 배치만 하면 되므로) 처음에는 (nCc * n-cCc * n-c-cCc ... *n-c-c...-cC0) * {(c!)**r}을 해주는 방법으로 생각 했다. 하지만 예제의 답이 나오지 않았고 여러 조합으로 해본결과 (nCr * n-rCr * n-r-rCr ... *n-r-r...-rC0) * {(r!)**c-1} 이런 방정식으로 답을 유도했다. 이 답을 유도하기위해 아래와 같은 작업을 해줬다, 아직 수학적 기술이 부족.. 백준 25919 Lost Edge 파이썬 최적화버전 https://www.acmicpc.net/problem/25919 25919번: Lost Edge 새로운 RPG게임인 Lost Edge에는 레이드 시스템이 존재한다. 하지만, 레이드에 참가하기 위해선 일정 레벨 이상을 찍고 레이드 장소에 모여야 한다. 플레이어는 상하좌우 4방향으로 한 칸씩만 움직 www.acmicpc.net https://77dptjd.tistory.com/48 이전 포스팅을 하고나서 코드를 다시 보니 굳이 find함수를 안 만들어도 됐었다. 처음 레벨업 탐색중에 레이드 장소에 갈 수 있다면 레벨업이 끝나고도 다시 갈 수 있기에 처음 레벨업 탐색중에 레이드 장소에 도달했다는 것을 표기해주는 변수를 하나 추가하면 find함수 없이도 문제를 풀 수 있었다. from collections .. 백준 25919 Lost Edge 파이썬 https://www.acmicpc.net/problem/25919 25919번: Lost Edge 새로운 RPG게임인 Lost Edge에는 레이드 시스템이 존재한다. 하지만, 레이드에 참가하기 위해선 일정 레벨 이상을 찍고 레이드 장소에 모여야 한다. 플레이어는 상하좌우 4방향으로 한 칸씩만 움직 www.acmicpc.net 대회 문제중에 풀만한 문제를 찾아보던중 발견한 문제였다. 일반적인 BFS와 다른 점은 heapq과 같이 사용한다는 것이였다. 왔던길을 다시 갈 수 있으므로 갈 수 있는 길을 모두 heapq에 담아 자신의 레벨보다 작은 몬스터들을 먼저 죽여 레벨업을 하면서 갈 수 있는 길을 넓여가면 된다. from collections import deque import heapq import sy.. 백준 1026 보물 파이썬 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 가장 작은 S를 구하기 위해서는 (첫번째 배열의 가장 큰값)*(두번째 배열의 가장 작은값)이 돼야 한다. 이 생각이 바로 떠올랐다면 매우 쉬운 문제였다. n =int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) a.sort() b.sort(reverse=True) re = 0 for i in r.. 이전 1 2 3 4 ··· 7 다음