본문 바로가기

Algorithm/Baekjoon

 (21)
Algorithm/Baekjoon Baekjoon #4796 - 캠핑 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 4796번 캠핑 2. 입출력 예시 입력 예시 출력 예시 5 8 20 5 8 17 0 0 0 Case 1: 14 Case 2: 11 3. 문제 풀이 주어진 입력/출력 예시를 통해 점화식을 세워보도록 하자. 휴가를 사용할 수 있는 총 기간이 20일이다. 그리고 이 중 연속된 8일은 2번(20 ÷ 8) 존재한다. 캠핌장 사용은 연속된 8일 중 5일만 사용 가능하므로 연속된 2일에 대한 캠핑장 사용 일수는 10일(20 ÷ 8 × 5)이다. 그렇다면 연속되지 않은 나머지 4일은 어떻게 될까? 이 역시 휴가 전과 후에 연속된 또 다른 8일이 존재한다. 즉, 나머지 4일은 캠핑장 사용 가능 일수 5일보다 작으므로 모두 캠핑장 사용이 가..
Algorithm/Baekjoon Baekjoon #1339 - 단어 수학 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1339번 단어 수학 2. 입출력 예시 입력 예시 출력 예시 2 AAA AAA 1998 2 GCF ACDEB 99437 10 A B C D E F G H I J 45 2 AB BA 187 3. 문제 풀이 이 문제는 딕셔너리를 활용하면 어렵지 않게 해결할 수 있다. 각 단어의 알파벳을 key로 설정 후 알파벳의 위치를 10의 제곱으로 나타내기로 하였다. 이를 표로 나타내면 아래와 같다. 단어 내용 GCD G(100), C(10) + D(1) ACEBF A(10000) + C(1000) + E(100) + B(10) + F(1) 위 표에 나타난 단어의 알파벳을 중복제거 후 값이 큰 순으로 정렬하면 아래와 같다. 이 알파벳 정렬..
Algorithm/Baekjoon Baekjoon #10162 - 전자레인지 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 10162번 전자레인지 2. 입출력 예시 입력 예시 출력 예시 100 0 1 4 189 -1 3. 문제 풀이 이 문제의 유형은 거스름돈과 동일했으며 딕셔너리를 사용하여 간단히 해결할 수 있었다. 문제를 해결하기 위한 순서는 아래와 같다. 딕셔너리(btn)의 각각 key를 버튼으로 하고 value를 0으로 초기화한다. 이때 각각 버튼은 모두 초 단위로 바꾸어주며, 초 단위가 큰 순으로 key에 저장한다. 냉동식품의 요리시간(T)를 입력받는다. 딕셔너리의 key를 기준으로 반복하며 해당 key의 value를 요리시간에 버튼의 초로 나눈 몫으로 변경하되 정수형이 아닌 문자열(str)로 변환한다. 이후 요리시간은 요리시간을 버튼의..
Algorithm/Baekjoon Baekjoon #1946번 - 신입 사원 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1946번 신입 사원 2. 입출력 예시 입력 예시 출력 예시 2 5 3 2 1 4 4 1 2 3 5 5 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 4 3 3. 문제 풀이 이 문제는 어찌보면 매우 간단하게 해결가능하나, 시간초과를 고려해야 하기 때문에 골치아픈 문제이다. 이 문제 흐름의 핵심은 정렬 후 값의 크기 비교이다. 서류심사 순위와 면접심사 순위가 주어지는데, 다른 사람들과 비교하였을 때 두 개 순위 모두 뒤처질 경우 탈락하는 방식이다. 즉, 둘 중 하나는 다른 사람들보다 높아야하므로 이를 알아보기 쉽게 서류심사 순위를 기준으로 오름차순 정렬을 해주어야 한다. 주어진 예시를 통해서 확인해보자. 먼저 5명인 ..
Algorithm/Baekjoon Baekjoon - #2217 - 로프 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 2217번 로프 2. 입출력 예시 입력 예시 출력 예시 2 10 15 20 3. 문제 풀이 일단 이 문제는 여러 번 틀렸는데, 그 이유는 문제의 출제 의도를 잘못 파악했기 때문이었다. 처음에는 여러 개의 로프 중 하중이 가장 작은 로프에 로프의 수만큼 곱하면 되겠다라고 생각했다. 여러 번 제출을 시도하였으나, 전부 틀렸습니다 처리를 받고 문제를 차근차근 몇 번이고 다시 읽어보았다. 중량 w의 물체를 여러 다발의 로프에 걸었을 때 각각의 로프에 걸리는 중량은 w/로프의 수량 이다. 예를 들어서, 로프 3개의 하중이 각각[20, 50, 100]일 경우를 생각해보자. 먼저 하중이 20인 로프의 경우를 보면, 최대 20 × 3개 ..
Algorithm/Baekjoon Baekjoon #1541 - 잃어버린 괄호 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1541번 잃어버린 괄호 2. 입출력 예시 입력 예시 출력 예시 "55-50+40" -35 3. 문제 풀이 이 문제 역시 간단히 해결할 수 있었다. 주어진 식의 합(total)을 0으로 초기화한다. 문자열로 구성된 식을 입력받으며, 이 때 +를 기준으로 나눈 후 이를 리스트(values)에 저장한다. 반복문을 통해 +를 기준으로 나눈 리스트의 요소를 다시 - 기준으로 나누어주며, 이때 나눈 요소들은 정수형(int)으로 변환 후 이들의 합을 리스트에 저장한다. 리스트의 길이만큼 역순으로 반복하며, 인덱스가 0일 경우 식의 합에 해당 해당 요소를 더하고, 그 외에는 식의 합에서 해당 요소만큼 빼준다. 인덱스가 0인 경우는 가장..
Algorithm/Baekjoon Baekjoon #5585 - 거스름돈 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 5585번 거스름돈 2. 입출력 예시 입력 예시 출력 예시 380 4 3. 문제 풀이 이 문제는 간단히 해결할 수 있었다. 문제를 해결하기 위한 과정은 아래와 같다. 타로가 지불해야할 금액을 입력받으며, 타로가 지불하고자 하는 1,000엔에서 타로가 지불해야 할 금액을 뺀 거스름돈을 변수 m에 저장한다. 각각의 동전의 종류(500, 100, 50, 10, 5, 1)를 리스트 변수(flags)에 저장한다. 동전 수량(cnt)은 0으로 초기화한다. 반복문을 통해 동전의 종류를 호출하고, 거스름돈에서 해당 동전을 나눈 몫을 동전 수량에 더한 후 거스름돈은 거스름돈에서 해당 동전을 나눈 나머지로 초기화한다. 모든 반복이 완료되면 ..
Algorithm/Baekjoon Baekjoon #1931 - 회의실 배정 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 1931번 회의실 배정 2. 입출력 예시 입력 예시 출력 예시 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 4 3. 문제 풀이 이 문제는 생각보다 까다로운 문제였다. 가정사항을 세운 후 수 차례 가정사항을 수정 후 문제를 풀 수 있었다. 회의의 수량(N)을 입력 받는다. 회의의 수량 만큼을 반복하여 각각 시작 시간과 종료 시간을 튜플로 받아온 후 이를 모두 하나의 리스트에 저장한다. 회의 수량(cnt)과 종료 시간(end)을 0으로 초기화한다. 리스트 내 튜플의 종료 시간을 기준으로 정렬 후, 시작 시간을 기준으로 다시 정렬한다. 반복문을 통해 리스트 내 튜플의 요소를 호출..
Algorithm/Baekjoon Baekjoon #11047 - 동전 0 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 11047번 동전 0 2. 입출력 예시 입력 예시 출력 예시 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 6 10 4790 1 5 10 50 100 500 1000 5000 10000 50000 12 3. 문제 풀이 이 문제 역시 굉장히 간단했다. 이를 해결하기 위한 순서는 다음과 같다. 동전 종류의 수량(N)과 가치의 합(K)를 입력받는다. 동전의 가치가 담긴 정보(A)를 입력받는다. 동전의 가치는 오름차순으로 주어지므로, 이를 내림차순으로 정렬한다. 반복문을 통해 동전의 가치가 담긴 리스트를 반복하며, 가치의 합에 동전 가치를 나눈 몫을 동전 수량에 더해준다. 그리고 가치의 합은..
Algorithm/Baekjoon Baekjoon #11399 - ATM 목차 1. 문제 2. 입출력 예시 3. 문제 풀이 1. 문제 백준알고리즘 문제 - 11399번 ATM 2. 입출력 예시 입력 예시 출력 예시 5 3 1 4 3 2 32 3. 문제 풀이 이 문제는 굉장히 간단했다. 이를 해결하기 위한 과정을 나열해보았다. 주어진 배열(P)을 오름차순으로 정렬한다. 새로운 배열에 주어진 사람의 수(N)만큼 반복하면서 배열의 순서 이전의 모든 값을 더한다. 새로운 배열 요소의 합을 출력한다. 이를 코드로 나타내면 아래와 같다. def solution(n, p): p.sort() t = [sum(p[:i+1]) for i in range(n)] print(sum(t)) N = int(input()) P = [int(x) for x in input().split(" ")] sol..

티스토리툴바