본문 바로가기

알고리즘

 (38)
python 백준1715 카드 정렬하기(BOJ1715) 문제링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 처음에 문제읽고 그냥 차례대로 쭈르륵 더하면 되는거아냐? 너무 쉬운데? 했다가~ 뭐지?? 하고 한두개 테스트 해봤더니 정말 답이 틀리게나온다! 그래서 규칙이 뭘까하고 한~~~참 고민하면서 적어보고 해서 겨우 해결했다.. 해결 아이디어는! 간단한데 글로 적으려니깐 쉽지않네..가장 요긴하게 쓴건 우선순위 큐! 입력으로 받은 카드들을 큐에 담고 앞에 두개 꺼내서 더한걸 다시 ..
python 백준1049 기타줄(BOJ1049) 문제링크 : https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 직접 적으면서 고민해보니 크게 어렵지는 않았다 이 문제는 예제 케이스도 많고 해서 다른사람들도 아이디어만 떠오른다면 오답없이 잘 통과할것같다 import sys input = sys.stdin.readline #끊어진 기타 줄 수, 가게 수 n, m = map(int, input().split()) set = [] single = [] #입력 for _ in range(m): a,..
python 백준13305 주유소(BOJ13305) 문제링크 : https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제가 길어서 처음에 보면 좀 당황스러울수 있는데 경험적으로 이렇게 문제가 길면 아이디어가 쉽게 나오는것같다. (뉴비수준의 문제일때) 그래서 어렵지않게 한방에 성공! import sys input = sys.stdin.readline #도시 수 n = int(input()) #거리, 주유소가격 distance = list(map(int,input().split())) o..
python 백준10610 30(BOJ10610) 문제링크 : https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 입력 숫자가 최대 105개의 숫자로 구성되어 있으므로 이것 숫자로 계산해서 풀게 아니라 문자열로 생각하고 풀어야될것같았다 이 문제의 핵심 아이디어는 - 입력숫자에 0이 포함 - 자릿수의 합이 3의 배수 인것같다 그리고 최대값을 구하는것이니 큰숫자부터 주르륵 나열하면 된다 그래서 아래와 같이 풀어서 제출을 했는데 import sys input = sys.stdin.readline inpu..
python 백준1463 1로 만들기(BOJ1463) 문제링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 처음에 풀때는 dp테이블 사용해서 반복문으로 풀면 되겠다 싶어서 제출했다 import sys input = sys.stdin.readline input_num = int(input()) dp = [0] * 1000001 #초기값 dp[2] = 1 dp[3] = 1 def cal(input_num): #3보다 작으면초기값 리턴 if(input_num
python 백준9655 돌게임(BOJ9655) 문제링크 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 이것도 간단한 문제여서 바로 풀었는데 자꾸 오답이 나와서 아주 스트레트 빡! 이었는데 알고보니 오타였다.. #돌개수 n = int(input()) if n%2 == 0: print("CK") else : print("SK") 이거 분명 맞는데?!!! 짝수면 창영이가 이기고 홀수면 상근이가 이기는게 맞는데? 왜그러지 했는데!!! 창영이를 CK이라고 해서 틀린거였다.. #돌개수 n = int(input()) if n%2 == 0: print("CY") else : print("SK") 으..짜정나
python 백준1010 다리 놓기(BOJ1010) 문제링크 : https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이문제는 조합 공식을 사용하면 바로 풀수있다 이런 문제들은 식만 뽑아낸다면 참 쉬운데 문제는 점화식을 못뽑아내면 손도 못대겠다는것.. 쨌든 이 문제는 처음에 math라이브러리를 써서 풀었었는데 그랬더니 메모리를 좀 잡아먹는것같아서 팩토리얼을 따로 정의해서 풀었다 import sys input = sys.stdin.readline #팩토리얼 def factorial(num): resul..
python 백준2748 피보나치 수 2(BOJ2748) 문제링크 : https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net for문에 별찍기가 있다면 dp에는 피보나치가 있다!@! 정말 가장 기본적인 구조인데 이 구조를 다른문제에도 적용하는게 어렵다.. 점화식을 구하고 어디까지 초기값으로 잡고 어느구간에서부터 반복문으로 돌릴지를 파악하는게 핵심인것같다 알면 뭐하나.. 잘 안되는걸ㅜㅜ import sys input = sys.stdin.readline #메모이제이션dp테이..

티스토리툴바