https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net DP문제로 아주 유명한 문제이다. DP가 큰 문제를 작은 문제로 나눠 생각해서 작은 문제를 통해 큰 문제를 해결하는 방식이므로 문제를 쪼개야한다. 예를 들어 1000원을 만드는 방법의 수를 구해야 한다면, 주어진 동전으로 1원을 만드는 경우의 수, 2원을 만드는 경우의 수, 3원을 만드는 경우의 수... 계속 나아가서 1000원까지 도달하는 방식으로 DP를 구성해 주면 된다...

드디어 백준 등급이 플래티넘이 되었다.이 solved.ac로 코딩을 처음 시작하고 브론즈 문제를 풀때가 떠오른다. 진짜 아무것도 아는거 없이 가장 입문하기 쉽다는 파이썬으로 시작해서 머리 박치기로 여기까지 왔다.그때는 코딩에 딱히 관심도 없었고, 컴공으로 진로를 정할지도 몰랐는데 이 솔브닥 사이트 하나가 인생을 바꿨다.남들 팀플할때 난 알고리즘만 공부했다. 딱히 특별한 이유는 아니고 그냥 알고리즘 푸는게 더 재밌어서 그랬다.골드1~플래5 구간이 레이팅200을 채워야 해서 정말 폐사구간인데 세그트리 덕분에 잘 넘겼다.세그트리 안쓰고 풀라 했지만 남은 레이팅 25를 앞두고 군대 훈련 일정 때문에 그냥 세그트리로 밀었다.   플래에 왔으니 이제 내실을 다질 차례이다. 골랜디를 하면서 내실을 다지고(아마 100..

https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다.www.acmicpc.net문제는 자신의 카드로 상대방의 카드를 나누어 떨어뜨릴 수 있으면 자신이 포인트를 1점 획득하고, 상대방이 내 카드를 나누어 떨어뜨리면 나는 1점을 잃는다. 그 이외의 상황에서는 점수 변화가 없다.문제는 N이 최대 100,000이라는 것인데 2중 포문으로 모든 플레이어와 한번씩 대결한 결과를 비교하면 시간초과가 난다.(C++은 1초에 1억개 정도의 연산을 수행한다) 그래서 에라토스테네스의 체와 비슷한 방식으로 ..

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제는 간단하다, 그냥 2차원 평면에 다각형이 주어졌을 때 넓이를 구하면 된다. 처음 문제를 보면 어떻게 구할지 이리저리 고민할 수도 있지만, 고등학교 수학시간에 신발끈 공식이라고 들어봤을 것이다. 신발끈 공식을 이용하면 무난하게 문제를 풀어 낼 수 있다. 라고 생각했지만 부동소수점을 조심해야한다. C++에서 소수점을 다루기 위해 fixed와 precision함수를 사용했다.우선 precision은 몇자리 까지 표기할 건지..

https://www.acmicpc.net/problem/25318 25318번: solved.ac 2022 첫 번째 경우에서 첫 번째 의견은 마지막 의견에 비해 약 $834$일 $6$시간$\,\approx 2.286$년 전 의견이므로, 가중평균은 \[X\approx\frac{\max\left( 0.5^{2.286},0.9^1 \right)\times 24+\max\left( 0.5^0,0.9^0 \right)\times 18}{\ www.acmicpc.net 맨처음에 문제를 봤을 때 C++로 "/"와 ":"를 어떻게 나눌까 고민이 많았다. 파이썬에서는 그냥 split을 사용하면 편하게 다룰수 있었는데 확실히 C++은 문자열 다루는 것이 좀더 어렵다. seperator로 분리해서 볼까도 했는데 굳이 그러..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 딱봐도 DP문제이다. 실버DP문제는 꽤 많이 풀어서 그런지 풀이가 한눈에 보인다. 해당 스티커를 선택할 수 있는 경우를 모두 고려해서 최대값을 dp값으로 저장하면 된다. 위의 경우를 점화식으로 작성하기만하면 끝이다. 스티커가 2줄이라 2차원 배열 쓰면 끝. 코드는 다음과 같다. #include #include #include #include #include #include #includ..