아리의 개발 일상

문제 -줄 수 있는 예산의 총액이 이 주어지고 그 총액이 넘지 않는 선에서 각 지방에 최대한으로 공급하고 한다. 입력 첫째줄에는 지방수 둘째 줄에서는 각 지방이 요청하는 예산 셋째 줄에는 총예산 출력 각 지방에 배정될 예산중 최대를 출력한다 풀이 가능한 예산값 v를 1부터 해서 증가해서 각 지방이 요청한 값보다 크면 그 지방이 요청한 값을 예산으로 정하고 작으면 v로 하여 총예산 보다 작은지 큰지 확인하면서 가능한 v의 최댓값을 구할 수 있다 다만 이렇게 하면 이 문제에서는 시간 초과로 나오기에 이분탐색 방법을 사용하여 좀 더 빠르게 구할 수 있다 이분탐색은 변수 s에 0을 변수 e에 지방이 요청하는 예산중 가장 큰 값으로 하여 (s+e)//2 중간값을 구하여 그 값을 기준으로 위의 과정을 돌려 총예산보..

문제 유제품을 3개를 한 번에 산다면 그중 가잔 싼 것은 무료 나머지 두 개의 제품 가격만 지불한다 한 번에 3개를 사지 않는다면 할인 없이 정가 지불해야 한다 입력 첫 줄에 유제품수 두 번째 줄부터는 각 유제품의 가격 출력 n개의 유제품을 살 때 최소 비용을 출력한다 예제 (3,2,2) (3) 이렇게 구입한다 문제풀이 1. 정렬을 이용하여 큰 수부터 정렬한다 2. 입력받은 유제품 가격을 루프를 돌려 3의 배수가 아닐 때 그 유제품 가격을 더한다 코드 n=int(input()) data=[] for i in range(n): a=int(input()) data.append(a) #유제품 가격 저장 data.sort(reverse=True) #역정렬 answer=0 count=1 while count

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나이트는 총 8방향으로 이동한다 현재위치가 (0,0) 일때 (1,2) (-1,2) (1,-2) (-1,-2) (2,1) (2,-1) (-2,1) (-2,-1) 그렇기에 bfs 알고리즘을 사용하여 현재 위치에 대해서 8방향의 이동을 모두 돌리고 이미 방문한 위치라면 이동하지 않게 만들었다 8방향으로 이동할때 주어진 체스판 넘어로 이동하지 못하도록 조건또한 추가해주어야한다. 알고리즘 1)체스판 범위 만큼..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.www.acmicpc.net가중치 없는 그래프가 주어질때 모든 정점 에 대해서 모든 정점으로 가는 길이 존재 하는 없는 지 구하는 문제로 플로이드 워셜 알고리즘을 사용했다 플로이드 워셜 알고리즘은 모든 정점에서 모든 정점으로 가는 최소 거리를 구할수 있게 해주는 알고리즘이다 입력 첫줄에 정점의 갯수 n 두번째 줄부터 n개 줄까지 서로 각 정점 i 에서 j로 가는 길을 있다면 1 없다면 0으로 주어진다 출력 i에서 j로 가는 길이 있다면 1 없다면 0으로 출..

https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 내용 각 국가마다 금 은 동 메달 획득수가 주어지고 우리가 찾고자하는 국가가 몇등인 찾는 문제이다 문제 조건은 입력 첫줄에 국가수 와 찾고자하는 국가 두번째줄 이후 부터는 그 국가의 번호와 메달 획득수를 금 은 동 메달 수로 차례로 나열한다 출력 찾고자하는 국가의 등수를 정수로 출력한 문제풀이 1) 모든 국가들에 대한 메달 정보들을 저장하고난후 금은동 메달 순으로 역정렬..