본문 바로가기
728x90

ALGORITHM142

[SWEA/Python] 1244. 최대 상금 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 앞 쪽에 위치한 숫자판보다 큰 숫자가 뒷쪽에 있다면 그 둘을 바꾸는 방법 → 32888 같은 경우에 틀리게 된다. 모든 경우의 수를 다 찾아서 비교해보자! → 재귀로 구현했으나 시간초과! 가지치기가 가능한가? 뒷 쪽 숫자가 더 클 경우에만 교환을 하는 방식 교환 횟수에 따라 따로 리스트에 값을 저장하여 중복을 방지 두 번째 경우엔 시간 초과없이 값이 잘 나왔다! 📌 코드 import sys sys.stdin = open('input.txt') def change(.. 2021. 10. 4.
[BOJ/Python] 1339. 단어 수학 📌 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 📌 문제 접근 방법 처음에는 맨 앞에 나온 알파벳에 가장 큰 숫자를 대입했다. 하지만, ''' 10 ABB BB BB BB BB BB BB BB BB BB '''​ 이러한 입력 값이 들어온다면 틀리게 된다. 따라서, 각 자리수마다 들어오는 알파벳을 리스트에 넣고 해당 자리의 값을 곱하여 계산하였다. 계산값이 가장 큰 값부터 큰 숫자를 대입하면 가장 큰 숫자를 찾을 수 있다. 📌 코드.. 2021. 10. 4.
[BOJ/Python] 1520. 내리막 길 📌 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 문제 접근 방법 이것저것 내 생각으로 할 수 있는 모든 시도를 다 해본 것 같다! (그냥 dfs, 방문 체크 리스트를 아예 가지고 다니기 등등) 결국 포기하고 구글링..! dp를 활용해야 하는 문제였다. 출발점에서 시작해서 도착점까지 도달할 수 있다면, dp 리스트에 값을 + 해준다. 이를 다 체크하면, (0, 0)에는 출발점에서 도착점까지 갈 수 있는 경우의 수가 남는다. 📌 코드.. 2021. 10. 4.
[BOJ/Python] 2960. 에라토스테네스의 체 📌 문제 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 📌 문제 접근 방법 2부터 N까지의 숫자 리스트를 생성한다. 가장 작은 수가 소수라면 그 수의 배수를 모두 리스트에서 제거한다. (나중에 생각하고 알게 된 점이지만, 어차피 가장 작은 수는 항상 소수이므로 소수판별을 생략해도 된다.) 📌 코드 def is_prime(number): for i in range(2, number): if not number%i: return False else: return True N, K = map(int, input().split()) nu.. 2021. 10. 4.
728x90

티스토리툴바