FandPROG FandPROG

컬러볼 문제 https://www.acmicpc.net/problem/10800 같은 색의 공끼리는 먹을 수 없고, 자기보다 크기가 작은 공끼리만 먹을 수 있을 때, 주어진 공이 공을 얼마나 먹을 수 있는지, 먹을 수 있는 공의 총 합을 출력하면 되는 문제이다. 입출력 형식 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다. N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다..

-쇠 막대기(10799, 백준) 기본적인 STL stack자료구조 응용 문제이다. '('이 들어올때는 stack에 push해주고, ')'이 들어오면 한 막대기가 완전히 잘린 것임으로 ans++을 해준다. 하지만 '('와 ')'가 연속해서 들어오는 경우 즉, 레이저가 들어오게되면, 현재범위에 있는 모든 막대기를 잘라야함으로, stack의 크기만큼 ans에 더해준다. 더보기 #include #include #include using namespace std; int l; char s[100010]; stack st; int main() { int i, j; scanf("%s", s); l = strlen(s); for (i = 0; i < l - 1; i++) { if (s[i] == '(' && s[i +..

-카드게임(10801, 백준) 구현 문제이다. 10개의 수가 들어간 배열을 2개 입력받고 비교하며, 더 큰수가 있는 쪽의 cnt값을증가시킨다. 그후, cnt가 더 큰쪽을 출력한다. cnt가 서로 같다면, D를 출력한다. 더보기 #include int a[15], b[15]; int a_win = 0, b_win = 0; int last_win = -1; // 1 = a, b = 2; int main() { int i; for(i=0;i

K번째 수문제  N*N배열 A를 오름차순으로 나열했을때 k번째수를 구하는 문제이다.입출력 형식첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. B[k]를 출력한다. 37 6아이디어 N범위가 10^5임으로, 배열을 구해 정렬하려면 O(N^2)즉, 시간초과가 난다. 따라서, 배열을 직접 구하는 대신에 다른 방법을 사용해야 한다. 이러한 방법을 생각해보자. 우선 문제에서 말하는 답을 ans라고 두었을때, 배열에서 ans보다 작거나 같은 수가 k개있을때, ans는 정답이 될 수 있다. 즉, ans보다 작거나 같은수가 k개임을 만족하는 ans의 값을 찾는 것이 이 문제의 핵심이라는 뜻이다. 그렇다면..

전단지 돌리기 문제 https://www.acmicpc.net/problem/19542 주어진 트리모양의 길 위에 전단지를 돌리는 문제이다. 힘을 나타내는 D보다 작은거리는 탐색하지 않고, 생각했을때의 최소 경로를 구해야되는 문제이다. 입출력 형식 첫째줄 노드의 수(1

-돌 게임 3(9657, 백준) 간단한 DP문제였다. 돌게임1과 똑같이 풀면 된다. 그냥 마지막 돌을 가져간 사람이 이김으로, 마지막 돌을 1로 두고 마지막 돌애서부터 1개 또는 3개 또는 4개 전의 돌중 하나라도 가져가면 지게 됨으로 0으로 두는 식으로 점화식을 세우면 O(N)만에 풀 수 있다. 이 문제도 수학으로 풀릴까 궁굼하다. 다음번에 돌게임 시리즈를 올려봐야겠다. >점화식> s1 >> s2; if (st.find(s1) == st.end()) st.insert(s1), mp.insert({ s1, idx++ }); if (st.find(s2) == st.end()) st.insert(s2), mp.insert({ s2, idx++ }); vec.push_back({ s1, s2 }); } for..

팰린드롬? 문제 https://www.acmicpc.net/problem/10942 주어진 배열의 (s, e)구간이 팰린드롬인지 판단하는 프로그램을 작성하는 문제. 입출력 형식 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다. 셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다. 넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다. 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. 7 1 2..

-돌 게임(9655, 백준) 간단한 DP문제였다. 그냥 마지막 돌을 가져간 사람이 이김으로, 마지막 돌을 1로 두고 마지막 돌애서부터 1개 또는 3개 전의 돌을 가져가면 지게 됨으로 0으로 두는 식으로 점화식을 세우면 O(N)만에 풀 수 있다. 처음에는 수학적으로 접근하다가 N범위가 적은걸 보고 그냥 DP돌렸다. 수학으로도 풀린다는 소문이있다. >점화식= 1; i--) { if (dp[i + 1] == 0) dp[i] = 1; else if (dp[i + 1] == 1) dp[i] = 0; if (i x) { ans++; s = arr[i]; } else s += arr[i]; } return ans; } int main() { long long i, j; scanf("%lld %lld", &n, &m)..