For Programmer

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 웰노운 그리디 문제이다. 사실 처음에 생각하기가 참 쉽지 않았다... 해당 풀이방법은 다음과 같다. 1. 첫번째 스위치를 킬때와 끌때를 기준으로 나눈다. 2. 두번째 스위치부터 마지막까지 돌면서 각 자리 스위치를 킬지 말지를 결정해야하는데 방식은 다음과 같다. 현재 스위치자리 한칸 앞의 스위치와 정답 스위치의 해당 자리와 전구 상태가 같은지 비교해서 다르다면 해당 스위..

https://www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 그리디 문제이나 그리디 문제들 특징이 처음보면 생각해내기가 쉽지않다는 것이다. 해당문제도 "참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다." 이 지문때문에 난이도가 상승하는데 사실 이지문이 있어도 모든 나무를 한번씩 자르는 것이 최대 이득이다. 왜냐하면 어차피 나무들은 냅두면 계속 자라기 때문에 가장 적게 자라는 나무부터 오름차순으로 계속 베어가면 ..

https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 처음에 전체를 N번 동안 돌고 각 반복문마다 앞에서 앞,뒤(i,i+1) 값을 보면서 앞의 값이 뒤의값보다 크다면 앞의 값을 (앞의값 - 뒤의 값 + 1)으로 바꿔주는 방식으로 생각했다. 다행이 N = 100이라 O(N^2)이 통과되었지만 N 이 10000이상일때도 해당 문제를 풀려면 O(N)방식을 생각해야한다. 따라서 그 방식이 뒤에서부터 값을 비교하며 만약 앞에값이 뒤값보다 더 크다면 해당 값..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 위 문제는 그리디적으로 접근해야하는데 실버4 치고는 처음에 사실 생각하기 꽤 어려웠다. 풀이법은 우선 오름차순 정렬한뒤 젤 작은값 * 총개수 , 그다음작은값 * (총개수 - 1) , ... 와같은식으로 계산한다음 가장 큰 값을 출력하는 식으로 접근하면 된다. 해당 문제의 증명은 각자 다들 잘 생각해보기 바란ㄷㅏ........ import sys input = sys.stdin.readli..

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 간단한 그리디 문제이다. 1부터 1씩증가시켜가면서 계속 더해가며 횟수를 센다. 만약 S와 같다면 그 횟수를 출력하면 되고 S보다 크다면 마지막 더한 횟수를 -1 해준 값을 출력하면 된다. S = int(input()) cur = 0 # 현재 값 i = 1 # 더할 값(1씩 증가) cnt = 0 # 더한 횟수 while True: cur += i # i만큼 계속 더한다 cnt += 1 # 횟수를 1씩 증가 if cur > S: # 만약 S보다 크다면 한개 줄이면 되므로 cnt -= 1 # 횟수를 1개 줄이고 brea..

https://www.acmicpc.net/problem/24956 24956번: 나는 정말 휘파람을 못 불어 '유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제 사실 골드 4 치고는 굉장히 어려운 문제이다. 접근 방법은 다음과 같다. 1. 누적합으로 W와 E의 개수를 미리 구해야 놓아야 한다. (단 E는 반대방향으로 누적합) 2. H를 만날때 마다 해당 H지점에서 왼쪽으로 W의 개수 * 2 ^ 오른쪽으로 E의 개수 - E의개수 - 1 로 구해야한다. 3. pow 내장 메서드와 3번 째인자 Mod 사용하면 더욱더 빠른 시간복잡도로 2 ** N 계산이 가능하다. 여기서 의문인 2 ^ 오른쪽으로 E의..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 간단한 투포인터 문제이다. 하지만 주의할 점은 문자의 종류가 N개 보다 작아도 최댓값을 갱신해주어야 한다. (문제에서 이부분에 대한 설명이 약간 부족했다. 이 부분을 테스트 케이스로 보여주면 좋았겠다.. ㅠ) alpha = [0] * 26 N = int(input()) word = input() + 'z' # 문자열의 범위를 벗어나지 않게 하기 위해 아무 문자로 패딩 s = 0 # 시작인덱스 e = 0 #..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 빠른 소수 구하기(에라토스테네스의 체 최적화) 2. 투포인터 (연속된 구간의 합) 위의 2가지를 이용하면 쉽게 문제를 해결할 수 있다. N = int(input()) # 빠른 소수 구하기 (에라토스 테네스의 체 최적화) sosu = [True for i in range(N + 1)] sosu[0], sosu[1] = False, False temp_sosu = [] for i in range(2, len(sosu)): if not sosu[i]: continue temp_sosu.append(i) index =..