Python43 [백준] 팩토리얼 0의 개수 https://www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net 1. 문제 이해 0의 개수가 m개가 되는 n!의 n을 찾는 문제 2. 문제 접근 5의 개수가 m개가 되는 팩토리얼을 찾아주면 되는 문제입니다. 그래서 처음에는 5의 배수 숫자들을 찾으면 5로 계속 나눠주면서 몇개의 5가 포함되어있는지를 찾았습니다. 하지만 이렇게 풀이를 하게 되면 시간 초과가 나게 됩니다. 중요한 포인트는 N보다 작은 수들 중에서 5로 나눠지는 숫자의 개수를 찾는 것입니다. 이를 찾는 가장 쉬운 방법은 5로 나눠보면 알 수 있습니다. ex) 41 -> 41 // 5 = 8(5, 10, 15, 2.. 2023. 11. 7. [백준] 창업 문제 링크: https://www.acmicpc.net/problem/16890 16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주 www.acmicpc.net 1. 문제 이해 구사과와 큐브러버가 사명을 정하는데 구사과는 사전순으로 가장 앞서게 하고 싶고 큐브러버는 사전 순으로 늦게 나오도록 하고 싶다. 각자 고른 알파벳 문자 N개가 있고 구사과를 시작으로 하나씩 문자를 배치할 수 있다. 최종적으로 N개의 알파벳을 배치하여 나온 사명을 알아내는 것이 문제의 목표입니다. 2. 문제 접근 deque를 활용하는 게임 이론인 것까지는 접근했.. 2023. 6. 18. [백준] 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 문제이해 마법의 두루마리에 적혀있는 단어의 문자순서대로 악마의 돌다리와 천사의 돌다리를 번갈아가면서 밟을 수 있는 모든 경우의 수를 구하는 문제입니다. 2. 문제접근 접근 방식: DP 제일 못하는 재귀 DP입니다. DP[k][i][j]라고 정의했을때 k = 0인 경우는 천사의 돌다리를 건널 차례일 때 마법의 두루마리의 i번째 문자를 돌다리에서 j인덱스부터 찾는 경우를 의미합니다. 재귀를 돌면서 돌다리를.. 2023. 5. 11. [백준] 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net BFS를 활용한 문제입니다. 가장자리(0,0)부터 BFS를 통해 사방탐색을 진행하면서 다음이 빈 공간이면 큐에 넣어주고 치즈이면 공기와 맞닿아있는 치즈이므로 cnt를 늘려준 다음 2이상인 치즈는 제거해주면 됩니다. import sys from collections import deque sys.stdin = open("input.txt", "r") input = sys.stdin.re.. 2023. 3. 23. [백준] 스크루지 민호 2 https://www.acmicpc.net/problem/12978 12978번: 스크루지 민호 2 구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 www.acmicpc.net 아이디어를 생각해내는데 꽤나 걸렸던 문제입니다. 포인트는 현재 노드로부터 도달할 수 있는 리프 노드까지의 경로 길이 중에 홀수 길이가 있는지를 알아야합니다. 현재 노드로부터 홀수 경로 길이라면 현재 노드에 경찰서를 세워주면 됩니다. 호 만약, 길이가 짝수라면 자식 노드에 경찰서가 이미 세워져 있으므로 세울 필요가 없기 때문입니다. import sys, heapq from collections i.. 2023. 3. 16. [백준] 원숭이 스포츠 https://www.acmicpc.net/problem/16438 16438번: 원숭이 스포츠 승민이는 동물원의 원숭이들을 관리하는 사육사입니다. 이 동물원에는 N마리의 원숭이들이 있고 원숭이들에게 1번부터 N번까지 번호를 붙였습니다. 7일간 동물원에서 원숭이들끼리 스포츠 경기 www.acmicpc.net 문제를 제대로 이해하지 못해서 조금 헤맸던 문제입니다. 이 문제의 포인트는 분할정복입니다. 절반으로 쪼개면서 현재 범위에서의 절반과 나머지 절반이 상대팀이 되도록 하면 됩니다. 예를 들어 n = 7일때, AAABBBB -> ABBAABB -> AABABAB순으로 팀을 나누어 주면 최소 한번은 다른 원숭이들과 상대팀이 될 수 있습니다. 7개의 팀 조합을 출력해야하므로 나머지 4개의 조합은 아무렇게나 출.. 2023. 3. 13. [백준] 모양 만들기 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net Flood Fill을 활용하여 풀이하였습니다. 각각의 그룹을 기록해주고 해당 그룹과 연결될 수 있는 빈칸들에 현재 그룹들을 set에 넣어줍니다. 그 다음 2차원 배열을 돌면서 현재가 빈칸이고 다른 그룹에 연결될 수 있는 후보 그룹들이 set에 저장되어 있으므로 해당 set에 저장되어 있는 후보 그룹들의 면적을 더해주면 현재 칸을 변경했을 때 얻을 수 있는 모양의 최대 크기가 됩니다. i.. 2023. 3. 9. [백준] 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체와 누적합을 활용하는 문제입니다. 먼저, 에라토스테네스의 체를 통해 n보다 작은 모든 소수를 구해줍니다. 그 다음 소수들을 누적합을 해가면서 check라는 set에 저장을 해줍니다. 현재까지의 누적합을 저장하면서 동시에 현재까지의 누적합에 n을 뺐을 때의 값이 check set에 들어있다면 연속된 소수의 합으로 만들 수 있는 경우가 됩니다. import sys input = sys.stdin.readline n = int(input()) check = set() def era(num): isPrim.. 2023. 3. 6. [백준] 인싸들의 가위바위보 https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 완전 탐색, 백트래킹으로 풀 수 있는 문제입니다. 침착맨이 다르게 낼 수 있는 모든 손동작의 경우의 수 n!에 따른 경기 결과를 직접 시뮬레이션해보면 됩니다. 제 풀이는 침착맨이 낼 수 있는 모든 손동작의 경우를 만든 다음 시뮬레이션을 하기 때문에 시간이 조금 더 걸리지만 백트래킹으로 직접 라운드마다 낼 수 있는 손동작을 그때 그때 지정하는 방식으로 풀면 조금 더 짧은 시간안에 풀이가 가.. 2023. 3. 3. 이전 1 2 3 4 5 다음