본문 바로가기

BOJ

 (110)
[BOJ][Python] 백준 20254번 - Site Score 문제 링크: https://www.acmicpc.net/problem/20254 20254번: Site Score Teams from variaous universities compete in ICPC regional contests for tickets to the ICPC World Finals. The number of tickets allocated to every regional contest may be different. The allocation method in our super region, Asia Pacific, is based on a para www.acmicpc.net 문제 풀이 $56U_{R}$ + $24T_{R}$ + $14U_{O}$ + $6T_{O}$ 코드
[BOJ][Python] 백준 22193번 - Multiply 문제 링크: https://www.acmicpc.net/problem/22193 22193번: Multiply Write a program that computes a product of two non-negative integers A and B. The integers are represented in decimal notation and have N and M digits, respectively. www.acmicpc.net 문제 풀이 두 번째 수와 세 번째 수랑 곱하면 된다. 코드
[BOJ][Python] 백준 2644번 - 촌수계산 문제 링크: https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 풀이 BFS를 이용해서 간단하게 구했다. 사람과 사람을 연결하는 간선의 가중치를 1이라 생각하고 거리를 구한다 생각하고 풀었다. 예외처리 해서 -1도 출력하면 된다. 코드
[BOJ][Python] 백준 2460번 - 지능형 기차 2 문제 링크: https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 문제 풀이 간단한 구현 문제이다. 내린 사람 수를 빼고 탄 사람 수를 더하고 max()를 써서 최댓값을 갱신했다. 코드
[BOJ][Python] 백준 1547번 - 공 문제 링크: https://www.acmicpc.net/problem/1547 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net 문제 풀이 간단한 구현 문제이고, 스왑을 이용했다. 공을 1로 생각하고 index()로 출력했다. 그리고 -1은 함정이다. 공이 없을리가 없다. 코드
[BOJ][Python] 백준 2101번 - 플러그 문제 링크: https://www.acmicpc.net/problem/2010 2010번: 플러그 첫째 줄에 멀티탭의 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연 www.acmicpc.net 문제 풀이 멀티탭에서 멀티탭을 연결하려면 한 멀티탭에 있는 플러그를 하나 써야한다. 그리고 마지막 멀티탭은 연결할 게 없으므로 멀티탭에 있는 모든 플러그를 사용 가능하다. 즉, 멀티탭의 플러그 수를 모두 더하고 멀티탭 하나 당 -1이니, (N-1)개의 플러그를 못쓴다. 그래서 합에서 (N-1)을 빼주면 된다. N이 최대 500,000이므로 빠른 입출력을 쓰거나 pypy로 돌..
[BOJ][Python] 백준 2254번 - 감옥 건설 문제 링크: https://www.acmicpc.net/problem/2254 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제 풀이 볼록 껍질 문제이다. 모노톤 체인 기법으로 풀었으며, 다각형 내부의 점 판정은 CCW로 간단하게 구할 수 있다. 볼록 껍질에 대한 자세한 내용은 나중에 직접 다룰 예정이다. 볼록 껍질을 만들 수 있을 때까지 반복문을 돌려주고, 먼저 가장 먼 외각의 볼록 껍질이 완성된다. Px, Py의 좌표(점을 $P_{xy}$라고 하자.)와 만들어진 볼록 껍질로..
[BOJ][Python] 백준 18870번 - 좌표 압축 문제 링크: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 풀이 set()과 딕셔너리로 풀었다. 먼저 집합으로 만들어서 중복된 숫자들을 지워주고 다시 리스트로 변환했다. 이후 다시 오름차순으로 정렬했는데, 꼭 정렬해줘야 한다. set()은 정렬을 고려하지 않기 때문에 정렬된 상태로 입력을 줘도 정렬이 안 되어 있을 수 있다. 어짜피 그렇게 안줄때도 있어서 하긴 해야한다. 이후 딕셔너리를 ..

티스토리툴바