Algorithm Study
-
[백준] 1940번 주몽Algorithm Study/Python 2024. 3. 22. 19:12
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 풀이 2개의 숫자를 더해 특정 숫자 M이 나오는지 확인하는 문제이다. N은 최대 15000이고 모든 경우의 수를 구하게 되면 15000 * 15000 / 2 정도가 나오기 때문에 시간 초과가 발생하게된다. 즉 더욱 단순하게 풀 수 있어야 하는데 이런 경우에는 투 포인터를 이용하여 양쪽에서 검사하면 쉽게 풀 수 있다. 입력 받은 숫자를 정렬한 뒤 양쪽에서 확인하면 현재 숫자..
-
[백준] 31416번 가상 검증 기술Algorithm Study/Python 2024. 3. 22. 19:01
https://www.acmicpc.net/problem/31416 31416번: 가상 검증 기술 현대오토에버의 가상 검증 기술은 차량·시스템·제어기를 가상화하고 가상 주행 환경, 검증 도구 등을 제공해 기능별 검증, 기능 간 연계 검증, 시스템 단위 검증을 하드웨어 없이 가상으로 진 www.acmicpc.net 풀이 입력의 테스트 케이스가 총 1000, 테스트의 갯수가 100, 최대 시간이 100이기 때문에 최대 100 * 100 * 1000의 시간으로 풀더라도 1억보다 작기 때문에 1초 안에 해결이 가능하다. 즉, 단순 구현으로도 수학적인 방법으로도 풀이가 가능한 문제이다. 먼저 단순 구현으로 풀어보겠다. 단순 구현으로 풀기 위해 실제 시간이 1씩 증가하는 방식을 사용하여 구현했다. while 문을 ..
-
[백준] 9655번 돌 게임Algorithm Study/Python 2024. 3. 17. 00:00
https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 풀이 두 사람이 돌을 1개 또는 3개씩 가져가면서 마지막 돌을 가져가는 사람이 이기는 게임이다. 두 사람이 1개 또는 3개의 돌을 가져갈 수 있는 경우는 1/1, 1/3, 3/1, 3/3 이고 서로 무조건 이기기 위한 선택을 하기 때문에 N번째에서 이긴 사람이 N+2, N+4, N+6에서도 모두 이기게 된다. 즉 홀수, 짝수로 나뉘어져 승리하는 인원이 정해진다. DP 기본적인 문제를 다시 풀려고 선택하였지만 단순한 문제가 되어버렸다. 전체 코드 N = int(input()) if N % 2 == 0: print('CY..
-
[백준] 20115번 에너지 드링크Algorithm Study/Python 2024. 3. 4. 00:49
https://www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 풀이 에너지 드링크가 가장 많은 양이될 수 있게 절반을 버리기 위해서는 항상 적은쪽을 버리면 된다. 가장 많은쪽을 버리지만 초기에 가장 많이 담겨있던 에너지 드링크를 버리지 않는 경우가 가장 적게 버리기 때문에 역순으로 정렬하여 풀었다. energys = list(map(int, input().split())) energys.sort(reverse = True) energys = deque(ene..
-
[백준] 1436번 영화감독 숌Algorithm Study/Python 2024. 2. 27. 22:17
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이 666이 들어간 숫자를 찾아서 해당 숫자가 몇번째인지 찾으면 되는 문제이다. 가장 단순하게 666(첫 등장)부터 1씩 증가하면서 666이 포함되어있는지 확인해서 풀었다. 전체 코드 N = int(input()) count = 0 for i in range(666, 100000000): if '666' in str(i): count += 1 if count == N: print(i) brea..
-
[백준] 2231번 분해합Algorithm Study/Python 2024. 2. 27. 22:12
https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 풀이 이 문제도 다양한 풀이 방법이 있을 수 있어 가장 직관적인 풀이와 시간을 단축시킬 수 있는 풀이로 구현해봤다. 1. 기본적으로 분해합을 처음 숫자 + 각 자릿수로 구현했기 때문에 해당 방법으로 직관적으로 구현할 수 있다. 숫자의 범위가 100만이기 때문에 문제 없이 풀 수 있다. N = int(input()) answer = 0 for i in range(1, N..
-
[백준] 2979번 트럭 주차Algorithm Study/Python 2024. 2. 27. 22:02
https://www.acmicpc.net/problem/2979 2979번: 트럭 주차 첫째 줄에 문제에서 설명한 주차 요금 A, B, C가 주어진다. (1 ≤ C ≤ B ≤ A ≤ 100) 다음 세 개 줄에는 두 정수가 주어진다. 이 정수는 상근이가 가지고 있는 트럭이 주차장에 도착한 시간과 주차장 www.acmicpc.net 풀이 특정 시간에 몇 대의 트럭이 주차되어있는지 알 수 있으면 계산하기 쉬운 문제이다. 시간 범위가 1 ~ 100까지기 때문에 100까지의 리스트를 미리 생성한 뒤, 입력으로 받은 범위에 차량이 있다는 것을 표시해주고 금액을 계산하면 된다. 전체 코드 A, B, C = map(int, input().split()) time_list = [0 for _ in range(101)]..