김머성 블로그

[BAE/<JOON> 문제풀이] 2550. 전구

https://www.acmicpc.net/problem/2550 2550번: 전구 첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력 www.acmicpc.net 핵심:: n log n LIS 알고리즘 풀이:: 스위치의 위치와 전구의 위치들의 상대적 인덱스를 배열로 만들고 LIS를 찾는다. 의견:: n log n LIS 문제가 플레 5인데 왜 그걸 응용한 이 문제 골드3인지 잘 모르겠다. 코드:: 더보기 #include #include #include #include using namespace std; struct trackball { int idx, val; }; ..

[BAE/<JOON> 문제풀이] 2602. 돌다리 건너기

https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 핵심:: DP 점화식 찾기 풀이:: DP 문제는 점화식 찾는거 밖에 적을 풀이 내용이 없음. dp배열 : dp[돌다리 번호][윗돌다리 : 0, 아래 돌다리 : 1][마법두루마리 글자 번호] = 해당하는 경로 갯수 점화식 : 현재 경로 개수 : sum(이전 경로 개수) if 현재 돌다리(n) 문자가 k번째 돌다리 문자와 같다면 -> dp[n][0][k] = sum( dp[0 ~ n - 1][1][k - 1] ..

[BAE/<JOON> 문제풀이] 1379. 강의실2

https://www.acmicpc.net/problem/1379 1379번: 강의실 2 첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번 www.acmicpc.net 핵심:: n log n 복잡도로 강의실 사용 추적 풀이:: 강의실 문제에서 백트래킹이 추가되었다. 방 개수 세는 로직은 같고 stl set으로 사용 가능한 방번호를 계속 추적했다. 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; str..

[BAE/<JOON> 문제풀이] 1943. 동전 분배

https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선 www.acmicpc.net 핵심:: 제한된 동전 개수 세기를 만족하면서 복잡도가 O(N^2) 안인 구현하기 풀이:: 우선 동전의 전체 가치가 홀수라면 동일하게 나눌 수 없으므로 시작전에 거른다. 남은 동전들로 전체 가치의 1 / 2 양을 채울 수 있다면 동일하게 나눌 수 있는 것으로 판단한다. 평소에 보통 동전 개수가 제한된 문제를 풀 때 동전의 개수만큼 해당 가치의 동전을 넣어서 0/1 Knapsack 문제를 ..

[BAE/<JOON> 문제풀이] 1365. 꼬인 전깃줄

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 핵심:: 주어진 전깃줄 위치들의 LIS(최장 증가 수열)을 구하면 자르지 않아도 되는 가장 긴 전깃줄 묶음을 구할 수 있다. 풀이:: LIS를 구하고 전체 전깃줄 수에서 빼면 잘라야하는 최소의 전깃줄 수를 구할 수 있다. 의견:: 새거 안 배우고 날먹으로 일지 채우는 거 같다. 그래도 1일 1새로운 알고리즘 문제는 에바임 진짜 코드:: 더보기 #define _CRT_SECURE_NO..

[BAE/<JOON> 문제풀이] 10422. 괄호

https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 핵심:: 카탈랑 수열 문제 풀이:: 괄호는 쌍을 이루어야만 올바른 괄호 문자열일 수 있으므로 입력된 N이 홀수인 경우 항상 0이다. 작은 N의 경우들을 계산해보면 (N / 2) + 1 번째 카탈랑 수를 출력해야함을 알 수 있다. 의견:: 코드:: 더보기 #include using namespace std; const long long vvv = 1000000007; long long dp[251..