728x90 반응형 Python169 2022.02.19 [백준] (python 파이썬) 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 동전을 coins에 담고 내림차순으로 배열한다. 이유는 필요한 최소 개수이기 때문에 큰 동전부터 계산해야하기 때문이다. coins배열을 for문을 돌려 큰 동전부터 k//i를 해서 몫을 구한다. 여기서 나오는 몫은 해당 코인의 필요한 개수이다. 그리고 나머지를 k에 대입한다. 1 2 3 4 5 6 7 8 9 10 11 12 13.. 2022. 2. 19. 2022.02.19 [백준] (python 파이썬) 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 1. m*n크기의 배열을 만든다. 2. 만든 배열에서 주어진 좌표에 맞게 사각형을 배열에 그린다. 3. for문을 돌려 사각형이 그려지지않은 부분을 찾은 뒤, bfs함수를 이용해 빈공간의 크기를 체크한다. 배열에서 그려진 사각형을 체크해야했다. 그래서 arr배열을 True로 초기화 시켜주었고, 사각형이 그려진 부분을 False로 바꿔주었다. 문제에서 사각형의 좌표를 줄때 .. 2022. 2. 19. 2022.02.19 [백준] (python 파이썬) N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 이 문제는 heap을 사용해서 해결했다. 문제에서 n*n의 표가 주어진다. 그리고 n번째 큰 수를 출력해야 한다. 모든 수를 heap에 저장 후, n번째 큰 수를 찾으면 메모리 초과가 발생한다. 그래서 첫 줄을 heap에 추가한다. 그러면 heap에 n개의 수가 들어가고 루트노드에는 최소값이 오게 된다. 그래서 다음 줄부터 값을 최소힙과 비교해서 최소힙보다 크면 pop후 큰 값을 push해준다. 모.. 2022. 2. 19. 2022.02.19 [백준] (python 파이썬) 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 이 문제는 최단 거리를 찾는 문제이기 때문에 bfs를 사용했다. 또한 최단 거리로 목표지점으로 가기위한 경로를 출력해야 했기 때문에 route배열을 이용해 해당 인덱스로 가기 위한 이전 인덱스를 저장했다. 1에서 출발해서 10까지로 예를 들면 아래와 같다. 1 2 3 4 5 6 7 8 9 10 0 1 2 4 5 위와 같이 배열에 이전의 위치가 저장되어있다. .. 2022. 2. 19. 이전 1 ··· 26 27 28 29 30 31 32 ··· 43 다음 728x90 반응형
