본문 바로가기

백준172

[Python] 백준 1759번 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 백트래킹 문제이다. 주어진 길이까지 백트래킹을 실시하고 주어진 조건만 맞추면 된다. 백트래킹의 기본이라고 볼 수 있다. ✔️ 느낀 점 브루트포스인 줄 알고 풀었는데 백트래킹 문제였다. 💻 코드 import sys l, c = map(int, sys.stdin.readline().split()) words = sorted(list(map(str, sys.stdin.readline().spl.. 2022. 7. 29.
[Python] 백준 1577번 : 도로의 개수 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 💡 문제 풀이 DP 문제이다. 이 문제는 메모리의 크기는 작긴 하지만 n, m의 100까지므로 배열을 사용해도 괜찮다. 최단거리로만 이동하기 때문에 항상 아래 혹은 오른쪽으로만 이동한다는 점이 포인트이다. 주어진 (a,b), (c,d)에 대해서 어떤 점이 못 가는 점인지 판단하기 까다롭다는 생각에 방향에 따라 이동 가능 여부를 따지려고 4차원 배열까지 가고 마지막 배열에 boole.. 2022. 7. 26.
[Python] 백준 2110번 : 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 입력받은 집의 위치를 정렬해서 이분 탐색을 진행한다. 이분 탐색 시 mid는 공유기 사이의 거리를 의미한다. 따라서 최소거리는 1, 최대 거리는 마지막 집과 처음 집의 간격이다. 지금 설치하려는 위치가 확인하는 간격(mid)을 벗어나는지 확인하면서 설치한 공유기 개수를 세어준다. 설치한 개수가 c보다 크다면 간.. 2022. 7. 26.
[Python] 백준 1300번 : K번째 수 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 메모리가 128MB까지고 배열의 크기가 100억이 될 수 있어서 반복문으로 메모리를 할당해서 풀 수 없다. 찾으려는 값 K보다 작은 값의 개수를 알면 K가 어디 있는지 알 수 있기 때문에 확인하는 값(mid)보다 작거나 같은 숫자를 세면서 이분 탐색을 진행해주면 된다. ✔️ 느낀 점 이분 탐색 문제는 풀면서 항상 느낀다. 아이디어를.. 2022. 7. 26.
[Python] 백준 2096번 : 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 메모리의 크기가 매우 작으므로 입력 값을 받는 동시에 최댓값과 최솟값을 따져준다. ✔️ 느낀 점 단순히 2차원 배열로 구현할 수 있다. 크게 어렵진 않지만 메모리 크기 때문에 조금 생각을 바꿀 필요가 있는 문제이다. 조금 바꾸는게 너무 어려웠다.. 💻 코드 import sys input = sys.stdin.readline n = int(input()) DP_max = [0] * .. 2022. 7. 22.
[Python] 백준 2225번 : 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 항상 절차대로 접근하면 된다. DP에는 i개의 숫자로 숫자 n을 만드는 경우의 수를 저장한다. DP[0]에는 0부터 숫자를 사용할 수 있으므로 몇 개의 숫자를 쓰던 경우의 수는 1이다. 표를 통해서 이해해 보자. 2를 2개로 만드는 경우는 (0, 2), (1, 1), (2, 0) 3가지이다. 이 경우는 (0을 한 개만 사용) * (2를 한 개만 사용) + (2를 한 개만 사용) * (0를 한 개만 사용) + (1을 한 개만 사용) * (1를 한 개만 사용) 이렇게 3가지로 볼 수 있다. 숫자 .. 2022. 7. 21.

티스토리툴바