알고리즘
-
[BOJ 1449, Python 3] 수리공 항승알고리즘/BOJ 2021. 8. 2. 12:58
https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 구멍이 난 곳마다 테이프를 붙여주는데 이때 테이프의 마지막 길이를 변수로 정해둡니다. 이 값을 val이라고 하고, arr[i] + 0.5 val이면 구멍을 막지 못했으니 테이프를 추가하여 val = arr[i] - 0.5 + l로 길이를 업데이트 해주면 됩니다. 예제는 정렬된 값이지만, 문제에서 정렬된 상태로 입력값이 주어진다고 나와있지 않아서 정렬을 했습니다. 코드 1 2 ..
-
[BOJ 13413, Python 3] 오셀로 재배치알고리즘/BOJ 2021. 8. 1. 13:48
https://www.acmicpc.net/problem/13413 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 방법 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다. 말 1개를 들어 뒤집어 놓아 색상을 변경한다. 풀이 이 문제는 두 가지 경우로 나누어서 풀 수 있습니다. 1) W, B의 개수가 같을 때 2) W, B의 개수가 다를 때 1) W, B의 개수가 같을 때 방법 1로 하는 것이 최적의 방법입니다. 왜냐하면 색깔이 서로 다른 부분만 확인해서 위치만 바꾸어주면 되는데, 서로 다른 부분의 개..
-
[BOJ 13305, Python 3] 주유소알고리즘/BOJ 2021. 8. 1. 13:27
https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 시작 도시의 기름값을 oil이라는 변수로 잡아두고 한 도시씩 이동하면서, i번째 도시의 기름값이 oil보다 작은지 확인해봅니다. 이때 기름값이 oil보다 작으면 oil의 값을 변경해주고 다시 한 도시씩 이동하면서 윗 줄을 반복합니다. 증명 일단 차가 무조건 이동해야하므로 처음 도시 기름 값을 이용해야 하는 것은 당연합니다. 그러다가 i번째 도시에 도착한 경우를 생각해봅시다. 1..
-
[BOJ 2847, Python 3] 게임을 만든 동준이알고리즘/BOJ 2021. 8. 1. 12:54
https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 풀이 arr[i] = arr[i+1]일 때 arr[i]는 arr[i+1] - 1이 되는 것이 가장 최소로 점수를 내릴 수 있는 방법입니다. 2중 for문을 하는 이유는 [5, 5, 3]이 입력 값으로 들어올 때 단순 for문으로만..
-
[BOJ 2217, Python 3] 로프알고리즘/BOJ 2021. 7. 31. 13:07
https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 이건 로프가 큰 것부터, 즉 내림차순으로 정렬하여 최대 무게를 찾아주면 됩니다. 내림차순으로 정렬하게 되면 이전까지의 로프가 버틸 수 있는 최대 중량이 현재 로프가 버틸 수 있는 최대 중량보다 무조건 크거나 같음을 보장하기 때문에 (현재 로프가 버틸 수 있는 최대 중량) * (지금까지 확인한 로프의 수)로 최댓값을 구할 수 있습니다. 코드 1 2 3 n = int(input()) a..
-
[BOJ 1783, Python 3] 병든 나이트알고리즘/BOJ 2021. 7. 31. 13:04
https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 문제를 읽어보면 if문을 참 많이 써야할 것 같은 생각부터 듭니다. 일단 N = 1일 때는 이동하지 못하므로 답은 무조건 1입니다. 그리고 위 아래로 두 칸씩 움직이냐 / 못 움직이냐로 나뉘어서 N = 2일때와 N >= 3일 때로 분기가 나뉩니다. N = 2일 때는 오른쪽으로 두 칸씩 이동하는 선택지만 가능합니다. 이것은 (M + 1) // 2로 이동횟수를 구할 수 있습니다. 그런데 문제에서 이동 횟수가 4칸 이상이면 모든 이동 방법을 한 번씩 사용해야하므..
-
[BOJ 1758, Python 3] 알바생 강호알고리즘/BOJ 2021. 7. 31. 12:56
https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 풀이 가장 큰 값부터 해결하는게 좋으므로 내림차순 정렬하여 풀음 코드 1234567n = int(input())arr = sorted([int(input()) for i in range(n)], reverse=True)ans = 0for i in range(n): if arr[i] - i
-
[BOJ 1543, Python 3] 문서 검색알고리즘/BOJ 2021. 7. 30. 18:38
https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 앞에서부터 단어가 있는지 확인하면서 답을 구하면 됩니다. 이게 왜 가능하냐면 만약 앞에 단어(A)가 있지만, 조금 뒤에 있는 단어(B)를 선택한다고 해봅시다. 그 후에 다음 단어(C)를 선택할 때, B를 선택했을 때 C가 선택 가능하다면 A를 선택하고 C를 선택할 수도 있다는 것입니다. 위와 같은 상황인 단어 A와 B. 그리고 다음 단어 D가 있다고 할 때, 단어 길이 때문에 B를 선택하면 D를 ..