https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net A를 세팅해놓고 B가 하나 들어갈때마다 얼마나 변화가 일어나는지 구하면 된다. 구하는 과정이 수학적이라서 수학 태그가 붙은거 같다. 특별한 코멘트가 필요 없는 평범한 그리디 문제이다. 코드는 다음과 같다. import sys input = sys.stdin.readline N, K = map(int,input().split()) if (N // 2) * (N - N//2) < K: print(-1) for i in range(..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 아주 유명한 well known 문제이다. 예전에 플레티넘 문제인 불 끄기에서 한번 접해봤던 문제이다. 그때 1열의 경우의 수에 대해서 1024가지를 고려했었다면 여기서는 첫번째 전구를 켜냐 끄냐로 나누어서 경우를 따져주어야한다. 여기서는 첫번째 전구 on off에 대한 것만 고려하면 되므로(2가지) 어렵지 않다. 그리고 앞의 전구가 만들려고 하는 전구와 다르면 버튼을..

https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 문제가 스택을 이용해야할거 같지만 풀이과정에서 굳이 스택이 필요한가 싶다. (물론 스택 자료구조에 대한 이해는 필요하다)4개의 스택이 있다고 했으니 크기가 4인 벡터를 만들어서 각각 스택의 최상위 값만 벡터에 담는 식으로 하여 스택없이 문제를 해결하였다.Greedy한 문제인데 풀이는 별로 어렵지 않다. 순열에서 숫자를 하나씩 꺼내서 벡터에 넣는데, 4개의 스택이라고 정해놓은 곳의 숫자보다 큰 값만 들어와야지 다시 일렬로 낼 수 있다.그 뜻은 순열이 숫자가 감소하는 부분이 5번 이상 나오면 스택에 넣을 자리가 없다는 ..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net C++ 연습을 위해 C++로 하려고 했는데 문자열 = 파이썬이라는 명언을 기억하고 파이썬으로 풀었다. 맨처음에는 최대로 문자열을 줄였을때 P가되면 PPAP문자열이다.라고 생각하고 코드를 짰더니 O(n^2)이 나와서 다시 지우고 다시했다. O(n)으로 즉 한번의 탐색만으로 문자열을 최대로 줄이기 위해 스택을 이용하였다.예를들어 PPPAPAP가 있다고 하면하나씩 스택에 넣다가 마지막 4개의 문자가 'P', 'P', 'A', 'P'이면 'P'로 만들어야..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net Greedy한 유형으로 핵심은 문자에 숫자를 대응하기 전에 모든 단어에 같은 알파벳이 얼마나 있는지가 중요하다. 처음에는 가장 왼쪽에 있는 알파벳부터 9를 대입하는 방식을 고안했는데 바로 틀렸다. 반례를 이러하다. ABBBBBB B BBB.....위으 경우와 같이 특정 개수이상 B가 계속 나오는 경우에는 A보다 B의 숫자가 더 커야지 최댓값이 되기 때문에 문자와 숫자를 대응하기 전에 자릿수를..

https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 와쿠컵에 출제되었던 문제다. 풀타임으로 하고 싶었지만 교수님께서 중간고사를 2번본다는 말씀을 하셔서 짝수번만 풀다가 음악을 좋아해서 문제 제목보고 풀려다가 한번에 못푼 문제였다. 틀린 문제들 다시 풀다가 이번에 풀었는데, 생각보다 너무 바로 아이디어가 떠올라서 허무했다. 왜 그때 한번에 떠올리지 못했을까...하이튼 그리디문제이고 별로 어려운 문제도 아니라고 생각한다. 풀이는 악보 수열을 받아서 연속..