부분합
-
백준 10800번 컬러볼 :: 마이구미알고리즘 풀이/수학 2017. 12. 21. 00:05
이 글은 백준 알고리즘 문제 10800번 "컬러볼" 을 풀이한다. 정올 초등부, 고등부에서 출제된 적이 있다. 본인의 푼 방식은 다른 풀이보다 속도면에서는 떨어진다. 문제 링크 - https://www.acmicpc.net/problem/10800 2019.10.10 수정 완료 지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다. 공 번호색크기 ..
-
백준 1644번 소수의 연속합 :: 마이구미알고리즘 풀이/수학 2017. 9. 10. 12:04
이 글은 백준 알고리즘 문제 1644번 "소수의 연속합" 을 풀이한다.접근은 에라토스테네스의 체를 통해 소수를 구하고, 투 포인터 또는 슬라이드 윈도우를 적용했다.투 포인터 및 슬라이드 윈도우의 개념은 중요하지 않다.본인 또한 구현하니 위와 같이 불리는 방식이였다.에라토스테네스의 체는 다음 링크를 참고하자.소수를 위한 에라토스테네스의 체 - http://mygumi.tistory.com/661644번 문제 - https://www.acmicpc.net/problem/1644 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+1..
-
백준 13900번 순서쌍의 곱의 합 [부분합] :: 마이구미알고리즘 풀이/수학 2017. 5. 21. 00:34
이번 글은 백준 알고리즘 문제 13900번 "순서쌍의 곱의 합" 을 다뤄본다.최근에는 서강대학교 프로그래밍 대회에서 출제된 문제이다.정답률이 30%이하로써, 단순히 쉬운 문제는 아닐 것이다.풀이 방법은 많겠지만, 부분합으로 일반적으로 접근할 수 있다. N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이 때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다. 처음에는 동적계획법 느낌으로 접근하려했다.2를 뽑을 경우 나머지 3, 4를 뽑을 수 있고, 3을 뽑을 경우 4를 뽑을 수 있다.쉽게 2개의 반복문을 통해 구현할 수 있겠다고 ..