728x90 전체 글129 백준 반복수[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. 백준 4-LSB [32685] 파이썬(Python) 코드 + 해설 1. 문제 소개스테가노그래피의 한 기법인 4-LSB를 이용하여, 척이가 은규에게 준 세 개의 십진수에서 화장실 비밀번호를 도출하는 문제다. 각 숫자의 4-LSB를 추출하고, 이를 이진수로 표현하여 순서대로 이어붙인 후, 다시 십진수로 변환하여 네 자리 비밀번호를 얻어야 한다.2. 문제 해결 방법입력받기: 세 개의 십진수를 입력받는다.4-LSB 추출: 각 숫자에 대해 4-LSB를 추출한다. 이는 숫자를 2진수로 변환한 후, 하위 4비트를 가져오는 것과 같다.이진수로 변환 및 이어붙이기: 추출한 4-LSB를 4자리의 이진수 문자열로 변환하고, 이를 순서대로 이어붙인다.십진수로 변환: 이어붙인 이진수 문자열을 십진수로 변환한다.비밀번호 생성: 변환된 십진수가 네 자리가 되도록 앞에 0을 붙여 비밀번호를 만.. 2024. 11. 18. 백준 대동여지도 [32339] 파이썬(Python) 코드 + 해설 1. 문제 소개세종이는 조선 시대의 지도인 대동여지도를 보며, 모든 지역을 연결하는 최소 비용의 도로를 설치하고자 한다. 도로에는 세 가지 종류가 있는데, 각각 도보 전용 도로(0), 말 전용 도로(1), 마차 전용 도로(2)이다. 세종이는 최소한의 비용으로 모든 지역을 연결하고자 하며, 만약 최소 비용의 방법이 여러 가지라면 주어진 우선순위에 따라 더 많은 우선순위의 도로를 포함하는 방법을 선택하려 한다.2. 문제 해결 방법이 문제는 최소 스패닝 트리(MST)를 찾는 문제다. 그러나 단순히 최소 비용의 스패닝 트리를 찾는 것에서 그치지 않고, 우선순위에 따라 도로의 종류를 최대화해야 한다.해결 전략은 다음과 같다:도로 우선순위 설정: 입력으로 주어진 도로 종류의 우선순위를 이용해 각 도로 종류에 대한 .. 2024. 11. 17. 백준 트리 장인 [32340] 파이썬(Python) 코드 + 해설 1. 문제 소개세종이는 정점 N개와 간선 M개로 이루어진 단순 그래프를 가지고 있다. 그는 이 그래프에 0개 이상의 간선을 추가하여 트리로 만들려고 한다. 간선을 추가할 수 있지만 기존의 간선을 제거할 수는 없다. 간선을 추가하는 방법의 가짓수를 구하고, 그 수가 K를 넘으면 −1을 출력하고, 그렇지 않으면 정확한 가짓수를 출력하는 문제다.2. 문제 해결 방법트리의 조건을 고려해보자. 트리는 사이클이 없는 연결 그래프다. 따라서 주어진 그래프를 트리로 만들기 위해서는 다음을 만족해야 한다:사이클이 없어야 한다: 기존 그래프에 사이클이 있으면 간선만 추가해서 트리로 만들 수 없다. 간선을 제거할 수 없기 때문이다.연결 그래프여야 한다: 모든 정점이 서로 연결되어 있어야 한다.따라서 주어진 그래프에서 사.. 2024. 11. 16. 백준 카드 뒤집기 게임 [32622] 파이썬(Python) 코드 + 해설 백준에 새롭게 추가된 한국어 문제 32622 카드 뒤집기 게임 정답 코드 및 해설입니다. 1. 문제 소개N개의 카드가 주어지고, 각 카드는 흰색 앞면(0) 또는 검은색 뒷면(1) 상태로 놓여있다. 우리는 선택적으로 처음 X개의 카드를 뒤집는 동작을 최대 한 번 수행하여, 뒤집은 후 카드 상태에서 연속된 같은 색상의 구간 중 가장 긴 길이를 점수로 삼는다. 카드 뒤집기 게임에서 얻을 수 있는 최대 점수를 구하는 문제다.2. 문제 해결 방법각 카드의 초기 상태(0 또는 1)가 주어진다.카드의 목표 점수는 뒤집기 후 연속으로 같은 색상(0 또는 1)인 가장 긴 카드 구간의 길이이다.최대 한 번, 1부터 X번 카드까지 뒤집을 수 있고, 이 때 X는 1 이상 N 이하인 정수다.뒤집기를 하지 않는 경우도 고려해야.. 2024. 11. 15. 백준 아카라카 2 [32652] 파이썬(Python) 코드 + 해설 문제 소개AKARAKA(아카라카)는 거꾸로 읽어도 같은 팰린드롬이며, 접두사이자 접미사인 "AKA" 또한 팰린드롬이라는 특징을 가진 문자열이다. 여기서 목표는 AKARAKA가 연속 부분 문자열로 정확히 K번 나타나는 가장 짧은 문자열을 찾는 것이다. 연속 부분 문자열은 원래 문자열에서 시작과 끝에서 문자를 임의로 제거하여 얻을 수 있는 부분 문자열을 뜻한다.예를 들어, K=1일 때는 "AKARAKA" 자체가 정답이 되고, K=2일 때는 "AKARAKARAKA"가 조건을 만족한다. 주어진 K값에 맞춰 AKARAKA가 중첩되도록 문자열을 구성해야 한다.문제 해결 방법AKARAKA가 정확히 K번 포함되도록 가장 짧은 문자열을 만들기 위해, 문자열의 중복을 최소화해야 한다. 이를 위해 첫 번째 "AKARAKA".. 2024. 11. 14. 백준 GLCCDM [32649] 파이썬(Python) 코드 + 해설 문제 소개양의 정수 𝐴, 𝐵, 𝐾가 주어질 때, 𝐾개의 서로 다른 양의 정수 수열 𝑑1 , 𝑑2 , ⋯ , 𝑑𝐾가 gcd ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐴 와 lcm ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐵를 만족해야 한다. 조건을 만족하는 수열을 찾고, 여러 개가 가능하다면 그 중 하나를 출력한다. 조건을 만족하는 수열이 없다면 -1을 출력한다.문제 해결 방법GCD와 LCM의 관계 활용:d1,d2,⋯ ,dK의 최대공약수 A와 최소공배수 B가 정해져 있기 때문에, 수열의 각 요소는 A의 배수여야 하며, 전체 최소공배수가 정확히 B가 되도록 구성해야 한다.조건 만족 여부 검토:B가 A의 배수가 아니면, 조건을 만족하는 수열이 존재할 수 없으므로 바로 -1을 출력한다.후보군.. 2024. 11. 13. 백준 gcd와 최단 경로 [32632] 파이썬(Python) 코드 + 해설 문제 설명정점이 1번부터 N번까지 있는 그래프가 주어진다. 두 정점 x와 y 사이에 간선이 존재하는 조건은 gcd(x,y)=1일 때이다. 즉, 서로소인 정점들 사이에 간선이 존재한다.정점 x에서 정점 y까지의 최단 경로 길이 dist(x,y)는 경로에 포함된 간선의 개수로 정의된다. 경로가 존재하지 않으면 dist(x, y) = 10^{10^{10}}으로 정의된다.정수 K가 주어질 때, 다음 조건을 만족하는 정수 x의 개수를 구해야 한다.1≤x≤Ndist(x,K)=gcd(x,K)문제 해결 방법이 문제는 각 정수 x에 대해 dist(x,K)와 gcd(x,K)를 비교하여 조건을 만족하는 x의 개수를 구하는 문제이다.그래프의 특성 분석간선의 존재 조건: 두 정점 x와 y 사이에 간선이 존재하려면 gcd.. 2024. 11. 12. 이전 1 2 3 4 ··· 15 다음 728x90
