백준 파이썬 코딩 (49) 썸네일형 리스트형 백준 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.. 백준 14268 회사 문화 1 파이썬 https://www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 처음에는 칭찬을 받을때마다 dp값을 갱신시켜줬었다. 하지만, 그렇게 했더니 시간초과가 났고 칭찬받은 칭찬의 크기를 저장해준뒤 부모노드를 저장한 배열을 자식노드를 저장한 배열로 바꿔준뒤 dp값이 0이 아니면 dfs를 돌려 re값을 채워줬다. 핵심 Key-word 1. 입력받을때마다 dp값을 갱신시켜주면 안 됨. 2. 부모노드를 저장한 배열을 자식노드를 저장한 배열로 바꿔줌. 3. dp가 0이 아닐.. 이전 1 2 3 4 ··· 7 다음