본문 바로가기

BOJ81

백준(BOJ) 16236 아기 상어(Python) BFS 문제. 아기 상어가 있는 위치로부터 같은 거리에 있는 물고기들 중 먹을 수 있는 물고기의 x,y좌표를 모두 저장한 뒤, 물고기의 좌표를 x,y좌표 순으로 오름차순 정렬해서 첫 번째 위치로 상어가 이동해 물고기를 먹는다. 만약 해당 거리에 물고기가 없다면 거리를 1 증가시켜 다시 물고기를 탐색한다. 나머지는 문제에서 주어진 대로 처리했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect """ import math from itertools import combinations from itertools import combinations_with_replaceme.. 2022. 8. 16.
백준(BOJ) 1424 새 앨범(Python) 구현 문제. 먼저 한 CD에 최대로 들어갈 수 있는 노래의 개수를 구해야 한다. 노래 사이에는 1초의 공백이 있기 때문에 CD의 길이를 (노래의 길이+1)로 나눈 몫을 구하고, CD의 길이를 (노래의 길이+1)로 나눈 나머지가 노래의 길이와 같다면 몫에 1을 더한다. 이 값이 한 CD에 최대로 들어갈 수 있는 노래의 개수이다. 이때 고려해줄 부분은, CD 하나에 최대로 들어갈 수 있는 노래의 개수보다 전체 노래의 개수가 더 작을 수 있다는 점이다. 따라서 둘 중 더 작은 값을 CD 하나에 최대로 들어갈 수 있는 노래의 개수로 설정한다. 만약 이 값이 13의 배수라면, 이 값에서 -1을 한 값이 한 CD에 최대로 들어갈 수 있는 노래의 개수이다. 그렇게 한 CD에 최대로 들어갈 수 있는 노래의 개수를 구한.. 2022. 8. 10.
백준(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.

티스토리툴바