백준 9465 스티커 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 문제의 경우 대각선으로 이동하는 경우 어떻게 많은 값을 가지고 이동할 수 있는가가 문제이다. 이전 퇴사 문제의 경우에도 선택하지 않을 경우가 있어서 스티커와 비슷한 문제라고 착각했다. 우선 조건부터가 많이 다르다. 퇴사문제의 경우 N이 1000개, 스티커의 경우 100000이다. 즉 일부분을 직접 방문해보면서 문제를 해결하기에는 시간초과가 발생한다는 의미이다. 그래서 dp..

백준 14501 퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사 문제이다. 각각의 걸리는 시간 만큼 일은 못하지만 그 사이에서 적절한 선택을 통해 최대의 수익을 올려야하는 문제이다. 이 문제를 풀면서 어려웠던 점은 다음 경우의 수를 선택안하고 다다음의 경우를 선택하여 최대의 수익을 올릴 수 있었다. 주의할 점 1. 무조건 다음 점이 아니라 다다음 점을 선택해도 최대가 될 수 있다는 점 1번을 해결하기 위해서 현재 위치에서 진행되는 시간을 더한 것 부터 최대 가능 시간까지 반복문을 돌렸다. 현재 위치 + 현재 업무가 걸리는 시간

백준 11052 카드 구매하기 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드 구매하기 문제의 경우 1장을 골랐을 때 최고의 가격, 2장을 골랐을 때의 최고의 가격 등을 구해주어서 문제를 해결할 수 있다. 아래의 예를 보자 10은 첫번째 카드, 9는 두번째 카드 ,,,, 쭉 진행한다. 1번째 카드의 경우 경우의 수가 1장 뿐이다. 2번째 카드 1 1, 2 자기 자체를 가지는 값 3번째 카드 1 2, 3 1번째 카드와 2번째 카드를 가졌을 때, 3번째 자기 자신..

www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이 문제는 M으로 나누어 떨어지는 구간을 구하는 문제이다. 카테고리를 보면 누적합이라고 되어있는데 누적합이라는 방법을 사용해서 간단하게 해결할 수 있다. 여기서 누적합이란 무엇일까? 누적합은 계속해서 덧셈을 해주어서 누적되어있는 구간을 만들고 그 누적합끼리 뺌으로써 원하는 구간의 합을 구할 수 있는 것을 의미한다. 위 그림을 보면 훨씬 쉽게 이해할 수 있다. 위 ..

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 문제다 언제나 그렇듯 O(N)을 반복하며 각 순간의 최적의 선택을 해주어야한다. 이 문제의 경우 조건이 두가지가 존재한다. 하나는 오른쪽 도시로 가는데 최적의 비용이고 거리의 길이만큼 무조건의 기름을 갖고있어야했다. 이 문제를 해결하기 위해서는 기준점이 되는 점의 기름 가격보다 더 적거나 같은 값의 가격이 나올 때 까지 반복문을 돌려 체크해준다. 더 큰 점의 경우에는 지나가며 거리를 저장해..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 해당 문제는 크게 어렵지는 않았다. trie의 특성을 이용해서 쉽게해결할 수 있다. 우선 문제를 해결하려면 현재의 온전한 문자를 접두사로 사용하는 곳이 있는지 체크해주어야한다. 트라이의 특성을 이용해 이 값을 다 찾으 다음 다음 후보군 노드 중에 NULL이 아닌 값이 있으면 해당 문자가 접두사로 이용되고 있음을 뜻한다. 아래 그림을 보면 간단할 것이다. 911을 찾을 때 911까지 찾은 ..