본문 바로가기

알고리즘연습/백준65

[BOJ] 21608번 상어초등학교 파이썬 문제 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생이 인접한.. 2022. 8. 13.
[BOJ] 2293번 동전1 파이썬 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 #dp 전체 문제인 k원을 구성하는 경우의 수를 구하는 것을 i원을 구성하는 경우의 수를 구하는 것으로 나누고, 이를 또다시 c원을 사용하는 경우에 i원을 구.. 2022. 8. 10.
[BOJ] 1789번 수들의 합 파이썬 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 풀이 #dp 처음에 dp배열에 합들의 값을 저장해줬었는데 그렇게 하니 메모리초과가 났다. 그래서 그냥 sum 변수에 값을 저장하는 방식으로 바꿔 풀었다. 가장 많은 개수의 자연수의 합이 되어야 하기 때문에 가장 잘잘하게(?) 합이 구성되어야 한다. 그렇기 때문에 1부터 더해줘야 한다고 생각을 했고, 이렇게 작은 수부터 더했을 때 sum이 S의 이상이 되면 그 인덱스 값을 저장했다. S와 같은 경우에는 index값이 정답이 되고 S 초과한 경우 딱 초과한 수만큼의 수를 1개 빼주면 .. 2022. 8. 8.
[BOJ] 14719번 빗물 파이썬 문제 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다. 출력 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고이지 않을 경우 0을 출력하여라. 풀이 #시뮬레이션 양쪽으로 블록으로 막혀있는 만큼만 물을 채울 수 있다. 따라서 블록이 양쪽으.. 2022. 8. 7.

티스토리툴바