본문 바로가기

ALGORITHM/백준67

[BOJ/PYTHON] 15656. N과 M (7) 백준 문제 링크: https://www.acmicpc.net/problem/15656 문제 요약 N개의 자연수 중에서 M개를 고른 수열 수열은 사전 순으로 증가하는 순서로 출력 고른 수열은 오름차순이어야 한다. 핵심 아이디어 기본적인 백트래킹 문제. 배열에 있는 숫자 하나씩 백트래킹을 돌면 된다. 풀이 # silver3-15656. N과 M (7) import sys input = sys.stdin.readline n, m = map(int, input().split()) nums = list(map(int, input().split())) nums.sort() array = [] def back(): if len(array) == m: print(*array) return for i in nums: a.. 2023. 7. 27.
[BOJ/PYTHON] 17136. 색종이 붙이기 백준 문제 링크: https://www.acmicpc.net/problem/17136 문제 요약 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이를 5개씩 가지고 있음 10×10인 종이 중 1이 적힌 칸 위에 색종이를 붙일 때 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수 핵심 아이디어 색종이를 5개부터 4, 3, 2, 1 순으로 붙였다가 떼어서 다 구한다. 모든 칸을 다 체크하는데, 백트래킹 함수에 x, y 좌표값을 받았다. 종이를 붙일 수 있는지 체크하고, 붙일 수 있다면 색종이를 붙이고 남은 종이 개수가 담겨있는 리스트에서 1을 뺀다. 백트래킹으로 다음 걸 봐주고, 종이를 뗀다. 풀이 # gold2-17136. 색종이 붙이기 import sys input = sys.st.. 2023. 7. 27.
[BOJ/PYTHON] 15811. 복면산?! 백준 문제 링크: https://www.acmicpc.net/problem/15811 문제 요약 복면산: 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐. 복면산 문제가 주어질 때 답이 존재하는지 여부를 출력 핵심 아이디어 입력에서 주어진 모든 알파벳에 0부터 9까지의 숫자를 경우의 수대로 다 넣어보고 되는지 확인하면 되는 브루트포스 문제이다. 같은 문자는 같은 숫자에 대응돼야 하고, 서로 다른 문자는 서로 다른 숫자를 나타내기에 알파벳을 딕셔너리로 관리하면 된다. 문자 하나가 숫자 한 자리를 의미하기에 입력으로 들어온 알파벳의 종류가 0~9의 10개를 초과하면 불가능하기에 바로 NO를 출력하면 된다. check 함수와 convert_word_to_num 함수를 만들었.. 2023. 7. 27.
[BOJ/PYTHON] 1759. 암호 만들기 백준 문제 링크: https://www.acmicpc.net/problem/1759 문제 요약 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성 암호는 알파벳순 정렬됨 사용했을 법한 문자의 종류 C가지가 주어졌을 때, 가능성 있는 암호 모두 구하기 핵심 아이디어 일반적인 백트래킹에 암호가 ‘사용했을 법한지’ 체크 로직을 넣으면 된다. 암호는 증가하는 순서로 배열되기에 정렬을 하고 시작한다. 풀이 # gold5-1759. 암호 만들기 import sys input = sys.stdin.readline l, c = map(int, input().split()) string = list(map(str, input().split()).. 2023. 7. 27.
[BOJ/PYTHON] 10597. 순열장난 백준 문제 링크: https://www.acmicpc.net/problem/10597 문제 요약 공백이 사라진 수열이 주어질 때, 복구된 수열 출력 순열은 1부터 N까지의 수로 이루어짐. 모두 10진수이고 공백으로 분리됨 핵심 아이디어 1부터 N까지의 수로 이루어진 “순열”이기 때문에 인풋의 길이로 순열의 마지막 숫자를 짐작할 수 있다. 인풋의 길이가 10보다 작으면 순열은 1부터 인풋의 길이까지만큼으로 이루어져있다. 인풋의 길이가 10보다 크면 1~9까지의 한 자리 수인 경우와 10부터의 두 자리 수인 경우로 나뉜다. 그러면 인풋의 길이에서 1~9의 경우인 9개를 뺀 후, 그 수를 2로 나누면 된다. 1~9를 뺀 나머지는 다 두 자리 수일 거라 2로 나누면 그 수들이 총 몇 개인지 나온다. 식으로 정리.. 2023. 7. 27.
[BOJ/PYTHON] 23304.아카라카 백준 문제 링크: https://www.acmicpc.net/problem/23304 핵심 아이디어 재귀로 풀면 된다. 현재 보는 문자열이 팰린드롬인지 체크하고, 맞다면 그 절반을 확인하면 된다. 왼쪽에서 절반과 오른쪽에서의 절반이 동일하다면 둘 중 하나(동일하니까)를 재귀를 돌리면 된다. 오른쪽 절반의 경우 string[half_len :]으로 한다면 홀수, 짝수인 경우의 수를 나눠 string[half_len + 1 :]도 커버해 줘야 하기 때문에 그냥 뒤에서부터 봐서 string[-half_len :]으로 했다. 풀이 # silver2-23304. 아카라카 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # 주어진 문자열이 아카.. 2023. 7. 27.

티스토리툴바