본문 바로가기

BOJ79

백준(BOJ) 2473 세 용액(Python) 이분 탐색 문제. 특성값을 받아서 오름차순 정렬하고, 왼쪽에서부터 조합으로 두 개씩 선정한 뒤 둘 중 더 큰 값을 기준으로 더 큰 값들에 대해 이분 탐색을 진행한다. 현재 특성값의 합이 지금까지 최소 특성값의 합보다 작은 경우 세 용액의 값을 수정한다. 이분 탐색의 경계값 수정 조건은 세 용액의 특성값의 합이 0보다 큰지 작은 지이다. 작다면 s=mid+1로 당기고, 크다면 e=mid-1로 당긴다. 이유는 너무나도 자명하다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import.. 2022. 8. 9.
백준(BOJ) 1005 ACM Craft(Python) 위상 정렬 문제. 일반적인 위상 정렬을 진행하되, DP를 이용해 각 노드까지 이동할 때 걸리는 시간을 갱신해줬다. 진입 차수가 0인 노드부터 시작해서 해당 노드의 건설 시간+해당 노드까지 이동할 때 걸리는 시간과 다음 노드까지 걸리는 현재 시간 중 더 큰 것으로 DP를 갱신했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import permutations import bisect input=sys.stdin.readline #sys.setrecursionlimit(1000000.. 2022. 8. 5.
백준(BOJ) 14500 테트로미노(Python) 브루트포스 문제. 블록 모양을 구현하기 위해 DFS를 사용했다. 길이가 4일 때까지 DFS를 하고, 길이가 4인 경우에는 이때까지 블록에 적힌 수의 합을 ans에 갱신한다. 그러나 위와 같이 DFS를 하면 그림의 보라색 블록을 커버할 수 없다. 따라서 보라색 모양은 따로 고려해서 DFS를 진행했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import permutations import bisect input=sys.stdin.readline #sys.setrecursionli.. 2022. 8. 4.
백준(BOJ) 1338 알 수 없는 번호(Python) 수학 문제. 입력받는 수가 양수인지 음수인지, 수의 범위가 모두 보장되어 있지 않기 때문에 이를 모두 고려해줘야 한다. 입력받은 범위에서 가장 작은 값을 기준으로, x로 나눈 나머지가 y인 가장 작은 값을 구한다. 그 수가 입력받은 범위 내에 존재하는지를 체크하고, 그 수에 x를 더한 값이 범위 내에 존재하지 않는다면 그 수를 출력하고, 그렇지 않으면 Unknwon Number를 출력한다. 코드는 다음과 같다. a,b=map(int,input().split()) x,y=map(int,input().split()) if x==0: print('Unknwon Number') elif y=abs(x): print('Unknwon Number') elif x>0: if a>b: a,b=b,a k=a%x if k 2022. 7. 30.
백준(BOJ) 7569 토마토(Python) BFS 문제. 일반적으로는 dx와 dy만 사용하지만, 이 문제는 dz도 사용해서 각 이동마다 고려해준다. queue에서 좌표를 한 번 꺼내고, 주변 토마토를 익게 한 다음 현재 익은 토마토의 개수가 전체 토마토의 개수와 같다면 break한다. 만약 위에서 break하지 못했다면 이는 모든 토마토를 익게할 수 없는 경우이다. 그 외에는 while문을 돌기 전 현재 익은 토마토의 개수와 전체 토마토의 개수가 같다면 0을 출력한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools impor.. 2022. 7. 30.
백준(BOJ) 1083 소트(Python) 그리디 문제. 0번 인덱스부터 n-2번 인덱스까지 값을 수정하는데, 각 인덱스가 남아있는 교환 횟수를 초과하지 않는 선에서 가장 큰 원소를 갖도록 수정한다. 교환 횟수는 당연히 (목표 인덱스)-(현재 인덱스)로, 목표 인덱스의 값을 교환을 통해 현재 인덱스까지 가져오는 횟수이다. 교환 횟수가 0이거나, 현재 인덱스의 값이 이후 인덱스의 모든 값보다 큰 경우를 예외 처리해줬다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations from itertools import permutations import bisect .. 2022. 7. 25.

티스토리툴바