728x90 Python/백준47 백준 울려퍼져라 [32764] 파이썬(Python) 코드 + 해설 백준 32774번 문제는 solved.ac기준 플레티넘 4입니다. 월간 향유회의 운영진들은 각자 가지고 있는 공을 이용해 게임을 하려고 한다. 게임의 규칙과 목표는 다음과 같다:각 운영진은 자신의 공을 모두 한 상자에 넣고 무작위로 섞는다.상자에서 공을 하나씩 뽑으며, 같은 운영진의 공이 연속으로 뽑힐 때마다 해당 운영진은 1점을 얻는다.게임은 여러 라운드로 진행되며, 각 라운드마다 참가하는 운영진의 범위가 주어진다.이번 글에서는 모든 라운드가 끝난 후 각 운영진의 점수의 기댓값을 효율적으로 계산하는 방법을 소개한다.1. 문제 이해하기1.1 게임 규칙 요약운영진 수: N명 (1≤N≤200,000)각 운영진의 공의 수: A1,A2,…,AN(1≤Ai≤5,000)라운드 수: Q개 (1≤Q≤200,00.. 2024. 11. 27. 백준 족보 검사하기 [32774] 파이썬(Python) 코드 + 해설 백준 32774번 문제는 solved.ac기준 플레티넘 4입니다.1. 문제 설명세종이는 자신의 가족 구성원들의 혈액형이 유전적으로 일관성 있게 전달되었는지 궁금해졌다. 가족 구성원의 혈액형과 일부 부모-자식 관계가 주어졌을 때, 모든 혈액형이 유전 규칙에 따라 올바르게 결정될 수 있는지 확인해보려고 한다.2. 문제 이해하기1.1 혈액형과 유전형의 관계혈액형은 A형, B형, AB형, O형 중 하나이다.유전형은 AA, AO, BB, BO, AB, OO 중 하나이다.각 유전형에 따른 혈액형은 다음과 같다:AA, AO ⇒ A형BB, BO ⇒ B형AB ⇒ AB형OO ⇒ O형1.2 부모로부터 자식의 유전형 결정각 부모의 유전형에서 하나씩 알레일(유전자)을 선택한다.선택한 두 알레일을 사전순으로 정렬하여 자식의 유전.. 2024. 11. 26. 백준 숫자 할당 [32825] 파이썬(Python) 코드 + 해설 백준 32825번 문제는 solved.ac기준 골드 4입니다.python3말고 pypy3로 해야 시간 초과가 안납니다. 1. 문제 설명이 문제는 5×5 크기의 격자판에 숫자를 배치하는 문제입니다. 변수 a부터 m까지 총 13개의 변수에 1부터 13까지의 숫자를 각각 한 번씩 할당해야 하며, 주어진 8개의 방정식을 만족해야 합니다.방정식은 다음과 같습니다:A=a+e+i+lB=b+f+j+mC=c+g+kD=d+hE=a+b+c+dF=e+f+g+hG=i+j+kH=l+m여기서 A부터 H까지는 주어진 정수입니다.2. 문제 해결 방법2.1 전체적인 전략백트래킹(Backtracking)을 사용하여 모든 가능한 숫자 할당을 탐색합니다.각 단계에서 현재까지의 할당이 방정식을 만족할 수 있는지 가지치기(Pruning)를 통해.. 2024. 11. 25. 백준 마법사 상어와 파이어볼[20056] 파이썬(Python) 코드 + 해설 1. 문제 해설마법사 상어는 크기가N×N인 격자에 파이어볼 M개를 발사한다. 각 파이어볼은 위치 (ri,ci), 질량 mi, 속력 si, 방향 di를 가진다.격자는 행과 열이 1부터 N까지 번호가 매겨져 있으며, 1번 행은 N번 행과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 즉, 격자는 토로이드 형태로 연결되어 있다.마법사 상어는 파이어볼에게 K번 이동을 명령하며, 각 이동마다 다음이 일어난다:모든 파이어볼이 자신의 방향 did_idi로 속력 sis_isi만큼 이동한다. 이동 중에는 같은 칸에 여러 파이어볼이 있을 수 있다.이동이 끝난 후, 2개 이상의 파이어볼이 있는 칸에서는 다음이 일어난다:같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.파이어볼은 4개의 파이어볼로 나누어진다.나누.. 2024. 11. 24. 백준 자석 체스[32334] 파이썬(Python) 코드 + 해설 백준 자석 체스 문제는 Solved.ac 기준 실버 1 문제입니다.1. 문제 해설자석 체스에서 세종이는 마지막 자석을 보드에 놓으려고 한다. 자석을 놓았을 때 다른 자석들과 붙지 않으면 승리하고, 붙으면 붙은 자석들을 모두 가져가야 한다.세종이가 이번 차례에 승리할 수 있는 위치를 찾고, 만약 없다면 가져가야 할 자석의 개수를 최소화하는 위치를 찾아야 한다.2. 문제 해결 방법효율적인 접근 방법 선택보드의 크기가 최대 1000이므로, 모든 빈 칸에 대해 붙는 자석의 수를 계산해야 한다.각 빈 칸마다 주변에 있는 자석의 수를 효율적으로 계산하기 위해 2차원 누적 합(Prefix Sum)을 사용한다.자석의 붙는 조건 분석자석이 붙는 조건은 행과 열의 차이가 각각 D 이하인 경우이다.즉, 어떤 자석의 위치가 .. 2024. 11. 23. 백준 하모니[32338] 파이썬(Python) 코드 + 해설 백준 32338 하모니 문제는 Solved.ac기준 골드 1 문제입니다. 1. 문제 해설한양이는 최대한 많은 기력을 얻고자 한다. 그는 수련의 조화 합이 0이 되면, 즉 양과 음이 균형을 이루면 총 기력이 두 배가 된다는 것을 알고 있다. 따라서, 각 수련을 선택하여 전체 시간 제한 내에서 최대의 기력을 얻는 것이 목표이다.제한사항 분석:수련의 수 T는 최대 100이다.총 시간 N은 최대 1000이다.각 수련의 시간 Wi는 최대 300이다.따라서, 동적 계획법(DP)을 사용하여 문제를 해결할 수 있다.2. 문제 해결 방법2.1 DP 테이블 정의dp[time][harmony_sum] = 최대 기력여기서,time: 현재까지 사용한 총 시간 (0 ≤ time ≤ N)harmony_sum: 현재까지 선택한 .. 2024. 11. 22. 백준 흑백 요리사[32653] 파이썬(Python) 코드 + 해설 1. 문제 해설성현이는 각 스테이크의 앞면과 뒷면을 같은 횟수로, 최소 한 번 이상 구워야 한다. 각 면은 한 번 굽는데 해당 스테이크의 두께 x_i분이 걸린다. 즉, 각 스테이크 iii는 한 면을 구울 때마다 정확히 x_i분을 사용하고, 총 구워야 할 시간은 2×x_i×n_i분이다. 여기서 n_i는 각 면을 구운 횟수이며, n_i≥1인 정수다.모든 스테이크는 동시에 불판에 올려지며, 중간에 제거할 수 없다. 또한, 굽는 도중에 스테이크를 뒤집는 시간은 각 스테이크의 두께에 정확히 맞춰야 한다.목표는 모든 스테이크를 "even"하게 굽기 위한 최소 시간을 찾는 것이다.2. 문제 해결 방법2.1 핵심 아이디어각 스테이크의 총 굽는 시간은 𝑇𝑖=2×𝑥𝑖×𝑛𝑖이다. 𝑛𝑖 는 각 면을 굽.. 2024. 11. 21. 백준 반복수[32687] 파이썬(Python) 코드 + 해설 백준 실버 3(Solved.ac) 문제번호 32687 반복수입니다. 1. 문제 소개하나의 K자리 수를 원하는 만큼 연속해서 이어 붙인 뒤, 뒤에서부터 0개 이상의 연속된 숫자를 제거하여 만들어낸 K자리 이상의 수를 K-반복수라고 한다. A 이상 B 이하의 K-반복수 중에서 M으로 나누어떨어지는 수의 개수를 구하는 문제이다.2. 문제 해결 방법이 문제는 K가 최대 6이므로 가능한 K자리 수를 모두 탐색해도 시간 내에 해결할 수 있다.해결 전략은 다음과 같다:K자리 수 생성:K자리의 수 S는 10^{K-1}부터 10^{K}-1까지다.이러한 S에 대해 무한히 반복된 문자열을 생성한다.반복된 문자열에서 가능한 길이의 접두어 생성:각 S에 대해 무한히 반복된 문자열 infinite_S를 생성한다.길이 L을 K부터.. 2024. 11. 20. 백준 제비통신 [32337] 파이썬(Python) 코드 + 해설 Solved.ac 난이도 : 실버 1 문제입니다1. 문제 소개한양이는 자신이 키우는 M마리의 제비 중 한 마리에게 편지를 묶어 세종이에게 보내고자 한다. 하지만 제비들은 각자 특정한 기울기를 가진 직선 경로로만 이동하며, 이 직선 경로 상에 세종이가 있어야만 편지를 전달할 수 있다.한양이와 세종이를 놓을 수 있는 N개의 좌표가 주어졌을 때, 제비 통신이 가능하도록 둘을 배치하는 모든 경우의 수를 구하는 문제다. 단, 한양이와 세종이는 같은 좌표에 위치할 수 없다.2. 문제 해결 방법이 문제는 두 점을 선택하여 그 사이의 기울기가 주어진 M개의 기울기 중 하나인 경우를 세는 문제다. 하지만 모든 점 쌍을 검사하면 시간 복잡도가 O(N^2)이 되어 제한 시간 내에 해결할 수 없다.이를 효율적으로 해결하기 위.. 2024. 11. 19. 이전 1 2 3 4 ··· 6 다음 728x90
