cs

CS/PS

    [BOJ] 2473번 : 세 용액
    CS/PS

    [BOJ] 2473번 : 세 용액

    • 문제 설명 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net KOI 2010 고등부 1번 문제이다. 푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 ..

    CS/PS

    [BOJ] 7578번 : 공장

    2013년도 KOI 도대회 고등부 3번 문제이다. 간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다. 해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다. 따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BO..

    CS/PS

    [BOJ] 2517번 : 달리기

    https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2012년도 정올 고등부 2번 문제다. segment tree와 좌표압축을 사용하면 된다. 실력을 기준으로 segment tree를 만들면 특정 실력의 선수를 확인할 때 O(logN)만에 최대 등수를 확인할 수 있다는 아이디어를 얻을 수 있다. 여기서 중요한 점은 앞에서부터 차례로 update를 해 주고 query를 처리하여서 i번째 선수까지만 tree에 반영이 될 수 있도록 하는 것이다. ..

    [BOJ] 10868번 : 최솟값
    CS/PS

    [BOJ] 10868번 : 최솟값

    https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net segment tree 개념 문제이다. 입력과 출력도 int 범위 내이고, update도 없으므로 크게 어려운 것 없는 문제이다. 다만 최솟값이라는 특성 상 initializing을 할 때 min(init(범위1), init(범위2)) 로 tree 값을 정해주고, query가 주어졌을 때에도 min(query(범위1), query(범위2))와 같은 형식으로 리턴..

    CS/PS

    [BOJ] 1781번 : 컵라면

    https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net priority queue(max heap)과 greedy 문제다. 중요한 아이디어는 앞 시간부터 데드라인을 계산하면 고려할 대상이 너무 많아지니 뒷 시간부터 데드라인을 계산하는 것이다. 만약 현재가 시간 t라면, 데드라인이 t보다 큰 모든 문제 중에서 가장 점수가 큰 문제를 골라서 해결하면 된다. 이 경우 시간 t까지 보았을 때 얻을 수 있는 점수 중에서 가장 큰 점수를 얻게 되므로 시간 1이 되었을 때..

    [BOJ] 1462번 : 퀴즈쇼
    CS/PS

    [BOJ] 1462번 : 퀴즈쇼

    https://www.acmicpc.net/problem/1462 1462번: 퀴즈쇼 첫째 줄에 문제의 개수 N과 보너스 점수를 얻는데 필요한 코인의 개수 M이 주어진다. (1 ≤ N, M ≤ 500,000) 둘째 줄에는 각 문제에 해당하는 점수가 1번 문제부터 주어지고, 셋째 줄에는 각 문제에 www.acmicpc.net 아주 재미있는 DP 문제이다. 얼핏 보면 2006정올 도대회 초등부 4번 '계단 오르기'(https://www.acmicpc.net/problem/2579)와 비슷해 보이지만 다르다. 처음엔 비슷한 문제로 보고 접근했다가 틀렸다. 가장 다른 점은 현재 풀고 있는 문제 i와 현재 가지고 있는 코인 개수 j를 가지고 2차원 DP table을 짜면 time complexity와 space ..

티스토리툴바