본문 바로가기

PS(Problem Solving)221

[백준] 1072번 - 게임 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 이분 탐색으로 승률이 오를 승수를 계산합니다. 승률이 증가했을 경우 ans 업데이트 후 범위를 줄이는 식으로 이분 탐색을 진행합니다. C++ 소스코드) 2022. 1. 20.
[백준] 14567번 - 선수과목 (Prerequisite) (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 - 선수과목 (Prerequisite) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 선수과목 제목보고 위상 정렬을 예상했으나 역시였습니다. 위상 정렬로 선수 과목을 탐색하면서 해당 과목을 들은 학기를 메모한 후 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/14567_%EC%84%A0%EC%88%98%.. 2022. 1. 20.
[백준] 1159번 - 농구 경기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 농구 경기 https://www.acmicpc.net/problem/1159 1159번: 농구 경기 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작 www.acmicpc.net 알파벳 배열을 만들어 문자열의 첫 글자만 확인하여 하나씩 세어주어 해결했습니다. C++ 소스코드) 2022. 1. 20.
[백준] 18427번 - 함께 블록 쌓기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 함께 블록 쌓기 https://www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 학생의 인덱스와 높이를 memoization을 진행합니다. 학생 수(N), 블록 개수(M), 높이(H)의 범위가 충분히 작아 O(N*M*H)의 시간 복잡도로 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2022. 1. 19.
[백준] 11562번 - 백양로 브레이크 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 건물의 수(n)가 250 이하이기 때문에 O(n^3)의 시간 복잡도를 가진 플루이드 와샬로 풀이가 가능합니다. 양방향 길은 모두 0, 일방통행 길은 한 방향은 0으로 나머지는 1로 부여해 플루이드 와샬을 진행합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2022. 1. 19.
[백준] 21924번 - 도시 건설 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 도시 건설 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다. C++ 소.. 2022. 1. 18.
[백준] 2745번 - 진법 변환 (C++) 문제 및 풀이 문제) 백준 - 구현 - 진법 변환 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문자열을 입력받아 진법 변환하는 쉬운 문제였습니다. C++ 소스코드) 2022. 1. 18.
[백준] 18312 - 시간 (C++) 문제 및 풀이 문제) 백준 - 구현 - 시각 https://www.acmicpc.net/problem/18312 18312번: 시각 정수 N과 K가 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 모든 시각을 세는 프로그램을 작성하시오. 시각을 셀 때는 디지털 시계를 기준으로, www.acmicpc.net 각 시, 분, 초를 완전 탐색합니다. C++ 소스 코드) 2022. 1. 17.
[백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 마라톤 2 https://www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 모든 체크 포인트의 좌표를 입력 받아 거리를 미리 계산합니다. 그 후, 체크 포인트를 뛰어넘는 경우와 그렇지 않는 경우로 각 최소 거리를 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10653_%EB%A7%88%EB%9D%BC%ED%86%A4%202... 2022. 1. 17.
반응형

티스토리툴바