본문 바로가기
반응형

백준 알고리즘12

[cpp 알고리즘] 백준 2170 선 긋기 [백준] 2170 선 긋기 cpp(c++) 풀이알고리즘: 정렬, 스위핑https://www.acmicpc.net/problem/2170문제 요약- 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.- 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다. (=> 선이 여러번 그련진 곳은 한 번씩만 계산한다.)- 이와 같은 식으로 선을 그었을 때, 그려진 선들의 총 길이를 구하는 프로그램 작성하기.풀이 정리- vector> 를 활용하여 각 점의 (시작점, 끝점)을 저장하였다. - 그리고 선을 그을 때, 인접한 두 선이 이어지는지 확인하기 위해 sort 를 활용해 정렬했다. - 이전 선의 시작점 인 경우에 이어질 수 있다고 판단했다. (아래.. 2024. 11. 11.
[cpp 알고리즘] 백준 3474 교수가 된 현우 [백준] 3474 교수가 된 현우 cpp(c++) 풀이알고리즘: 수학, 정수론https://www.acmicpc.net/problem/3474문제 요약- 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 구하기풀이 정리-  2의배수*5의배수로 0이 생기는데, 2의 배수는 많기 때문에 5의 배수의 최대 개수를 구하면 된다. ex) 60!의 경우는 5의 배수(60/5 =12)와 25의 배수(60/25=2)의 개수를 합친 12+2=14 로 답이 14가 나온다.C++ 코드#include #define ll long longusing namespace std;ll T, N;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0.. 2024. 11. 10.
[cpp 알고리즘] 백준 17827 달팽이 리스트 [백준] 17827 달팽이 리스트 cpp(c++) 풀이알고리즘: 수학, 구현https://www.acmicpc.net/problem/17827문제 요약- 선형 단방향 연결리스트로 1번 부터 N번 노드까지 연결되어 있다.- 이 때, N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 생기는 연결 리스트를 이룬다. - 이 때 K번 노드에는 어떤 값이 있을지 구하는 문제이다. 풀이 정리- 연결리스트가 된 이후에 K번째 값들을 나열해 보았고, 아래와 같은 수식을 얻을 수 있었다.- k번째 값이 (V-1)보다 작으면 (=연결되지 않는 부분)이면 해당 인덱스의 값을 출력해주면 된다.- 그 외의 경우는, 반복되기 때문에 V번째로부터 (K-(V-1)) % (N-(V-1)) 만큼 떨어져 있는 값을 출력해주면 .. 2024. 11. 9.
[cpp 알고리즘] 백준 20005 보스몬스터 전리품 [백준] 20005 보스몬스터 cpp(c++) 풀이알고리즘: 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비우선탐색https://www.acmicpc.net/problem/20005문제 요약- 지도의 크기(M, N)과 플레이어의 수(P)가 주어진다. - 지도에는 .(이동할 수 있는 길), X(이동할 수 없는 길), 알파벳 소문자(플레이어 아이디), B(보스 몬스터) 위치가 주어진다.- 각 플레이어의 아이디(알파벳 소문자)와 dps(1초당 얼만큼의 보스몬스터의 체력을 줄일 수 있는지)가 주어지고, 보스 몬스터의 HP가 주어진다.- 모든 플레이어들은 보스몬스터의 위치로 최대한 빠른 경로로 이동하며, 이동한 경우 공격을 바로 시작한다. (공격에 소모되는 시간, 상/하/좌/우 한 칸을 이동하는 데 소요되는.. 2024. 11. 8.
반응형

티스토리툴바