알고리즘/백준 문제 풀이 (338) 썸네일형 리스트형 [Python] 2758번 로또 https://www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 23/03/13 전형적인 2차원 DP문제로, 만약 DP가 아니라 백트래킹으로 접근한다면 시간초과가 날 수도 있을 문제이다. 문제 접근 방식: $\mathrm{DP}$문제를 접근할 때에는 먼저 상태를 정의하는게 우선이다. 이 문제에서는 영향을 미치는 요소가 $n$과 $m$ 두가지 라는 사실을 알 수 있다. 때문에 다음과 같이 상태를 정의해보자. $\mathrm{DP}[i][j]$ $=$ 선영이가 지금까지 $.. [Python] 1563번 개근상 https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 23/03/09 3차원 DP문제로, 상태를 정의하기만 하면 점화식을 구성하는 것은 그렇게 어렵지 않아서, 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 문제를 자세히 보면, 개근상을 받을 수 없는 경우를 주목해야 할 필요가 있다. 개근상을 받을 수 없는 경우는 $N$일 중에서 지각이 $2$회 이상이거나, 결석이 연속 $3$회 이상이면 개근상을 받을 수 없다. 반대로 말하면, $N$일 중에서 지각이 $1$회 이.. [Python] 1229번 육각수 https://www.acmicpc.net/problem/1229 1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 23/03/09 조금은 독특한 방식의 DP문제로, 문제에서 주어진 정보를 적극 활용하여 미리 전처리를 해 시간을 대폭 줄여야 하는 문제이다. 만약 문제에서 주어진 정보가 없었더라면 조금은 더 까다로웠을 지 모른다. 이전에 도전했다가 시간초과를 여러 번 받아 실패했던 문제로, 이 글을 통해 도움을 받았으면 좋겠다. 문제 접근 방식: 이 문제는 캡틴 이다솜 문제와 유사한 방.. [Python] 2421번 저금통 https://www.acmicpc.net/problem/2421 2421번: 저금통 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다. 홍태석은 www.acmicpc.net 23/03/12 전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다. 문제 접근 방식: 문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다. 이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수.. [Python] 22770번 Ellipse Intersection https://www.acmicpc.net/problem/22770 22770번: Ellipse Intersection Input may contain multiple test cases. The first line is a positive integer n (n ≤ 100), denoting the number of test cases below. Each case is composed of two lines, the first one is the description of orbit A, and the second one the description of orbit www.acmicpc.net 22/12/31 전형적인 수학문제로, 극좌표로 적분을 해야하는 문제이다. 극좌표 적분에 관한 내용은 미적분학.. [Python] 1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 22/12/05 플로이드-워셜이나 BFS응용으로 풀 수 있는 문제로, BFS응용풀이에 대한 아이디어는 14217번과 같은 아이디어를 공유하고 있다. 2022.11.29 - [백준 문제 풀이] - [Python] 14217번 그래프 탐색 [Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 142.. [Python] 1107번 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 22/12/04 조금 생각해야되는 브루트 포스 문제로, 조금만 생각한다면 그리디 알고리즘으로도 풀 수 있을 것 같다. 문제 접근 방식: 이 문제는 두가지 방법으로 풀 수 있다. 어떻게 하면 최소버튼을 누르게 만드는 번호를 찾을 수 있을까?로 접근한다면 그리디적인 접근으로 푸는 것이고, 그냥 생각 없이 채널 번호를 $0$부터 $1,000,000$까지 확인하면서 돌리면 브루트 포스로 .. [Python] 26006번 K-Queen https://www.acmicpc.net/problem/26006 26006번: K-Queen 재헌이는 생일 선물로 크기가 $N \times N$인 체스판과 백색 킹 하나, 흑색 퀸 $100\ 000$개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상 www.acmicpc.net 22/12/01 그룹 연습 문제로 나왔던 문제를 풀었다. 실버 3치고는 개인적으로 어려웠던 편에 속해서, 실버 2로 충분히 올라가도 될 것 같다. 문제 접근 방식: 전형적인 구현 문제이지만, 구현을 잘 못한다면 어렵게 돌아갈 가능성이 존재한다. 먼저, 나는 흰색 킹이 8방향으로 움직일 수 있다는 점에 착안하여, BFS를 구현할 때처럼 dr, dc배열을 선언해주었.. 이전 1 ··· 21 22 23 24 25 26 27 ··· 43 다음
