전공
-
백준 4190(Exact Change)전공/알고리즘 2020. 10. 25. 14:22
www.acmicpc.net/problem/4190 4190번: Exact Change The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer, the price in cents of the item you would like to buy. The price will not exceed 10 000 cents (i.e., \$100). www.acmicpc.net 진짜 한 스무번 제출한 문제 dp문제인데 이것 역시 나한테 엄청 도움이 되었던 문제인것 같다. 정해져 있는 금액이고, (0~MAX) 그 ..
-
백준 15487(A[j]-A[i]+A[l]-A[k])전공/알고리즘 2020. 10. 23. 12:24
www.acmicpc.net/problem/15487 15487번: A[j]-A[i]+A[l]-A[k] 크기가 N인 배열 A가 주어졌을 때, i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 구하는 프로그램을 작성하시오. www.acmicpc.net 구현이 진짜 어려웠던 문제 난 아직 인덱스 처리가 익숙치 않나보다. 생각정리만 좀 하면 바로 풀 수 있는 문제를 진짜 한 세네시간 헤맨듯? 단순하게 쪼개서 생각해주면 된다. 0~1까지 최대 0~j까지 최대를 저장하고, j+1 ~ N까지 최대를 하나하나 저장한 뒤에 인덱스를 잘 지지고 볶아서 j는 1에서 N-2까지 이동하면서 최대를 출력하면 된다. 지금 생각해보니 더 쉬운것 같기도? #include..
-
백준 11062(카드게임)전공/알고리즘 2020. 10. 22. 14:58
www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 음 바로 직전에 푼 문제와 거의 동일한 문제이다. 그래도 얘기를 좀 해보면 dp를 어떻게 설정할지가 중요하다. 이것 역시 dp는 이중배열로 했고, dp를 배열하나로 값을 지정할 경우 그리디화 된다고 해야되나 그런 느낌이 든다. 1개를 뽑았을때의 최댓값 이런식으로 값을 구하려고 하면 그리디스럽다 그냥 기분이 실제로는 잘 모르겠다. 그래서 dp[i][j]에서 i, j까지 뽑았을때의 최댓값을 저장한다. 그러고 나서 내 ..
-
백준 1053(팰린드롬 공장)전공/알고리즘 2020. 10. 22. 13:09
www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 진짜 대단하다 컴퓨터는 이 문제를 풀면서 컴퓨터는 진짜로 대단하다는 걸 느낀다. 사람이라면 조건을 다 따져서 하드코딩해야 하는 것을 컴퓨터는 그냥 다 해보면 된다. 그리고 dp는 더 아름답다. 이 문제는 dp이다. 태그에서 찾았기 때문에 dp인걸 알았지만 어떻게 풀어야 할지 감이 안 왔었다. 그러다가 그냥 하면 되지 않나 생각이 드는 순간 감이 왔다. 일단 우리는 팰린드롬인지 아닌지를 생각할 필요가 별로 없다. 이게 ..
-
백준 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로 풀 수 있다는데 아직 생각을 해보질 않아서 감은 안온다. 근데 그리디로도 가능하다 모든 문제가 그리디로 가능할 수 있다고 말할지도 모르겠지..
-
백준 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 중에 죽은 애..