전체 글
벽 부수고 이동하기 - [백준 2206번]
벽 부수고 이동하기 - 백준 2206번 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,..
타일 채우기 - [백준 2133번]
타일 채우기 - 백준 2133번 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 풀이 dp[1] n = 3 일 때, 경우의 수 : 3 dp[1] = 3 dp[2] n = 4 일 때, 경우의 수 : 11 dp[1] * dp[1] + 2 ( 새로운 모양 2개 ) dp[3] n = 6 일 때, 경우의 수 : 41 dp[1] * dp[2] + dp[2] * 2 ( dp[2] * 새로운 모양 ) + 2 ( 새로운 모양 2개 ) dp[4] n = 8 일 때, 경우의 수 : 153 dp[1] * dp[2] + dp[3] * 2 ( dp[2] * 새로운 모양[2] 2개 ) + dp[2] *..
캥거루 세마리2 - [백준 11034번]
캥거루 세마리2 - 백준 11034번 문제 캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇 번 움직일 수 있을까? 입력 여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) 출력 각 테스트에 대해 캥거루가 최대 몇 번 움직일 수 있는지 출력한다. 풀이 그리디 알고리즘?? 코드 import sys def threeKangaroo(a, b, c): a, b, c = sorted([a, b, c])..
전자레인지 - [백준 10162번]
전자레인지 - 백준 10162번 def microwave(second): button = [5 * 60, 1 * 60, 10] # 전자레인지 시간조절 버튼(단위 - 초) result = [] time = second if time % 10 != 0 : return -1 result.append(str(time // button[0])) # A버튼 갯수 time %= button[0] result.append(str(time // button[1])) # B버튼 갯수 time %= button[1] result.append(str(time // button[2])) # C버튼 갯수 return ' '.join(result) # 출력 형태 : 0 0 0 '''테스트'..
세탁소 사장 동혁 - [백준 2720번]
세탁소 사장 동혁 - 백준 2720번 문제 미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 동혁이는 리암에게 실망했다. 리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다! 어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다. 거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈..
신입사원 - [백준 1946번]
신입사원 - 백준 1946번 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램..
도서관 - [백준 1461번]
도서관 - 백준 1461번 문제 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수 계산하는 프로그램 작성 세준이는 0에 위치, 책도 전부 0에 반납 한 걸음에 1칸씩, 최대 M권을 들 수 있고, 다시 0으로 돌아올 필요 없다. 입력 첫째 줄 - 책 개수 N, 한 번에 들 수 있는 책의 개수 M 둘째 줄 - 책의 원래 위치 출력 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수 코드 import sys '''' 왼쪽(음수)과 오른쪽(양수)로 나뉨 책들 모두 들면 다시 돌아와야하기 때문에 *2 책을 모두 제자리에 두고 그 자리에서 끝나기 때문에 최대값에서는 *1만 하기 때문에 책의 최대 거리 * 2 - 최대값 으로 계산함 ''' def solution(M, originLocations): result = 0 '..
강의실 - [백준 1374번]
강의실 - 백준 1374번 문제 N개의 강의 최대한 적은 수의 강의실을 사용하여 모든 강의 진행 한 강의실에서 동시에 강의 진행 불가 종료시간과 시작시간이 같아도 상관 없음 필요한 최소 강의실의 수 출력 입력 첫째 줄 - N : 강의 갯수(1
배 - [백준 1092번]
배 - 백준 1092번 문제 항구에서 배에 화물을 실어야함 모든 화물은 박스에 들어있음 항구에는 크레인 N대, 1분에 크레인당 한개씩만 실을 수 있음 모든 크레인은 동시에 움직임 입력 첫째 줄 - N : 크레인 수 둘째 줄 - 각 크레인의 무게 제한 ( 1,000,000 보다 작거나 같음) 셋째 줄 - M : 박스의 수 넷째 줄 - 각 박스의 무게 ( 1,000,000 보다 작거나 같음) 출력 모든 박스를 배로 옮기는데 드는 시간의 최솟값 출력 코드 import sys def solution(craneWeightLimits, boxWeights): result = 0 craneWeightLimits.sort(reverse=True) # 내림차순 boxWeights.sort(reverse=True) # 내..