포스팅
-
백준 14890 경사로 (Python)알고리즘 2023.10.10 11:36
크기가 N * N 인 지도에서 각 행과 열마다 길을 놓을 수 있을 때 조건에 맞게 만들 수 있는 길의 개수를 구하는 문제입니다. 길이 완성되는 조건은 다음과 같습니다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 합니다. 높이가 차이나는 길은 경사로를 놓아서 길을 만들 수 있습니다. (경사로의 높이는 항상 1입니다.) 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야합니다. 낮은 칸과 높은 칸의 높이 차이는 무조건 1이어야 합니다. 경사로를 놓을 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 합니다. 경사로를 놓을 수 없는 조건은 다음과 같습니다. 경사로를 놓은 곳에 또 경사로를 놓는 경우 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 낮은 지..
-
백준 17251번 힘 겨루기알고리즘 2023.03.06 10:42
문제 설명 이번 문제는 N명의 참가자들을 나열하고 기준선을 통해 팀이 나눈 다음 각 팀에서 가장 힘쎈 사람이 나왔을 때, 둘 중 더 힘 쎈 사람이 이기게 됩니다. N 명의 참가자의 힘을 나타내는 정수가 주어질 때, 이길 확률이 더 높은 팀을 구하는 문제입니다. 문제 풀이 아이디어 가장 힘 쎈 팀 구하는 방법 기준선이 어디에 있는지에 상관없이 항상 가장 힘이 갖아 쎈 사람이 있는 팀이 이기게 됩니다. 가장 힘이 쎈 사람이 한 명일 경우 가장 힘이 쎈 사람의 인덱스를 i라하면, 기준선이 1~i-1일 경우 블루팀이 이기고, i~N-1일 경우 레드팀이 이기게 됩니다. 여기서 두 팀이 이길 확률을 구해보면, 블루팀은 (i-1)/N이고 레드팀은 (N-i)/N입니다. 그러므로 두 팀 중 이길 확률이 높은 팀은 i-1..
-
백준 11000, 2457 문제 풀이 (Feat. 그리디 & 파이썬)알고리즘 2024.03.08 14:37
백준 11000번 강의실 배정 문제 설명 N개의 강의 중 i번째 강의가 si시간에 시작해 ti에 끝이난다. 최소의 강의실을 사용하여 모든 강의를 배정하는 방법을 구하는 문제입니다. 문제 풀이 모든 강의를 배정할 수 있는 최소 강의실 개수를 구하는 문제이므로 언제 강의실의 개수가 늘어나는지를 살펴보면됩니다. i번째 강의를 배정할 때 강의실의 개수가 늘어나는 경우는, 현재까지 생겨난 강의실의 마지막 강의가 끝나는 시간이 i 강의의 시작 시간보다 모두 늦은 경우입니다. 기존 강의실에 배정할 수 있는 경우 새로운 강의 C의 시작시간 S3가 두 강의실의 마지막 강의가 끝나는 시간 T1, T2 중 T1보다 크므로 강의실 1에 강의 A가 끝난 뒤 배정하면 됩니다. 새로운 강의실을 배정해야 하는 경우 새로운 강의 C의..