분류 전체보기
-
백준 19576(약수)전공/알고리즘 2020. 10. 17. 15:00
www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 요즘 자면서 많이 생각한 문제이다. dp[]인걸 알아야 하는 문제인것같다. 일단 정렬을 해서, 지금 최대 몇 개의 배수 약수 관계인지 찾으면 된다. 찾으려면 일단 N^2의 시간이 걸린다. 왜냐하면 각기 다른 것들끼리 비교를 해야되기 때문에. 이걸 그러면 어떻게 비교해야할지 생각하면 어딘가에 저장해서 dp[]를 이용해서 밑에서 부터 위로 올리면 편할 것 같다는 생각이 든다. 예시에서 24 10 4 6 3 이렇게 있는데 이걸 오름차순 정렬하면 3 4 6 10 24 이렇게 되고, 여기서 3부터 시작한다. 3은 그 전 어떤 것과 나누어떨어지..
-
백준 19591(독특한 계산기)전공/알고리즘 2020. 10. 14. 20:04
www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 음 자료구조,구현 문제인것 같다. 그리고 stoll함수에 대해서 알고 있으면 좋을듯? 일단 스트링으로 받는다. 그 뒤에 숫자와 연산자를 따로 저장. deque에 저장하면 아주 좋을것같아서 deque를 처음으로 사용해보았다. 그 뒤에 주어진 연산기능 그대로 구현을 하면된다. 구현과정은 좀 까다로울수있다고 생각한다. 어떻게 구현할지 잘 생각하고, 구현하는게 관건인 문제였다. 아 그..
-
백준 20047(동전 옮기기)전공/알고리즘 2020. 10. 14. 15:30
www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T �� www.acmicpc.net dp로 풀자 밑에 ㅈㄴ 더러운 풀이임 걍 스킵추천 ------------------------------------------------------------------------------------------------------ dp로 풀 수 있다는데 아직 생각을 해보질 않아서 감은 안온다. 근데 그리디로도 가능하다 모든 문제가 그리디로 가능할 수 있다고 말할지도 모르겠지..
-
2020 ICPC 지역예선 후기대회/ICPC 2020. 10. 11. 11:04
일단 같은 학회원 pkpete님과 bbk0723님과 대회에 참여하였다. 우리는 프린트가 되지않는 환경이었기에.. 본인의 실수로 예약을 잘못함 모두 같은 문제를 동시에 A~L까지 훑어보고 논의 후 쉬우면 바로 한명 코딩으로 진행하였다 A Ball Alignment 정렬에 대한 문제였다. 오름차순으로 정렬을 해야하는데 오른쪽 끝 아니면 왼쪽 끝으로만 이동 할 수 있고, 횟수 몇 번이 최소이냐를 구하는 문제였는데 어려웠다 왼쪽으로 보내는 조건과 오른쪽으로 보내는 조건을 계속해서 찾으려 했지만 보이지 않았고, 알 수 있었던 건 최대 N-1번이면 정렬이 된다는 사실 하나? 그렇게 쉬운 문제를 넘긴다는 불안함을 가지고 B로 패스 B Bit String 이 문제를 보는 중에는 사실 A를 내가 계속 보고 있었기 때문에..
-
백준 6166(Meteor Shower)전공/알고리즘 2020. 10. 10. 01:31
www.acmicpc.net/problem/6166 6166번: Meteor Shower There are four meteors, which strike points (0, 0); (2, 1); (1, 1); and (0, 3) at times 2, 2, 2, and 5, respectively. t = 0 t = 2 t = 5 5|. . . . . . . 5|. . . . . . . 5|. . . . . . . 4|. . . . . . . 4|. . . . . . . 4|# . . . . . . * = meteor impact 3|. . www.acmicpc.net 구현 문제.. 그냥 bfs이다. 딱 봐도 그렇다 왜냐 턴제 문제이기 때문에, 메테오가 충돌하고, 원래 남아있던 bessie 중에 죽은 애..
-
백준 11998(Milk Pails)전공/알고리즘 2020. 10. 9. 16:38
www.acmicpc.net/problem/11998 11998번: Milk Pails (Silver) Farmer John has received an order for exactly \(M\) units of milk (\(1 \leq M \leq 200\)) that he needs to fill right away. Unfortunately, his fancy milking machine has just become broken, and all he has are two milk pails of integer sizes \(X\) and \(Y\) www.acmicpc.net 주어진 행위를 할 때 그 행위를 할 수 있는 횟수가 주어져 있고, 그 횟수 이내에서 가장 적절한 값을 찾는것이 문제. 주어..
-
백준 11687(팩토리얼 0의 개수)전공/알고리즘 2020. 10. 7. 16:08
www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net 0이 어떻게 만들어지는지에 대한 문제이다. 어떤 n!을 파보던 2의 거듭제곱 갯수가 5의 거듭제곱 갯수보다 항상 많으므로 n!에서 0은 5의 거듭제곱 갯수가 결정한다. 5의 거듭제곱 갯수의 합을 구하면 되는 문제이다. #include using namespace std; #define MAX 100000000 int sum; int main() { int M; cin >> M; for (int i = 1; i
-
백준 1005(ACM Craft)전공/알고리즘 2020. 10. 7. 15:11
www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬 문제이다. 위상정렬은 연결된 그 전 행위에 대해서 모두 마쳤을때 그 노드로 이동할 수 있는 그래프에 대한 순서이다. 위상정렬 알고리즘으로는 순서도 알 수 있고, 그 노드까지 실행하는데 필요한 최소값 최댓값 이런 것을 알 수 있다. 이 문제는 어떤 행위를 하는데 걸리는 최솟값에 대한 문제이다. 그래프 구성을 한 뒤에 진입차수 위상정렬 알고리즘을 이용해서 최솟값을 결정하도록 하자 그래프 구성은 단순..