For Programmer

https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 간단한 정렬 문제이다. x축 기준 정렬하여 x축 중간값 찾고 y축 기준정렬해서 y축 중간값을 찾는다. 그 후 반복문을 돌면서 거리를 계산해주면 된다. import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] arr.sort(key=lambda x: x[0]..

https://www.acmicpc.net/problem/19590 19590번: 비드맨 구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 www.acmicpc.net 딱 코드포스 같은곳에서 좋아할 문제이다.. N이 아주 크고 그리디.... 아이디어 생각하기 정말쉽지 않은 문제이다. 단 생각하고나면 간단하다. 가장 큰 값과 총 합을 찾는다. 만약 (총합 - 가장 많은 구슬의 개수) - 가장 많은 구슬의 개수 가 음수라면 즉, 가장 많은 구슬의 개수를 제외한 나머지 구슬들의 합이 더 적다면 그냥 가장 많은 구슬의 개수 - 나머지 구슬 개수의 합이 답이다. 그러나 반대로..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net import sys input = sys.stdin.readline from collections import deque # 사과를 먹으면 뱀길이 늘어남 # 벽이나 자기지신의 몸과 부딪히면 게임 끝 # 뱀은 0,0 시작 길이는 1 처음엔 오른쪽 # 1.다음칸에 몸길이 늘려서 이동 # 2-1.사과가 있으면 사과 사라지고 꼬리는 그전칸 그대로 # 2-2.사과 없으면 꼬리를 끌고와서 몸길이 그전 그대로 유지 ..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 아이디어 구상하는것이 처음에 되게 까다로웠다. 몇번의 케이스를 직접 쓰다보니 다음과 같은 정보를 얻을 수 있었다. 만약 해당 i번째의 값보다 그 앞 i - 1번째까지의 합 + 1 것보다 작거나같다면 무조건 i번째까지 합한 값은 무조건 측정이 가능하다는 것이다. 즉, 1 2 3 8 가있을때, 첫번째 1 보다 2번째 2가 1+ 1와 같기 때문에 총 합인 3까지는 무조건 측정이 가능하다는것이다. 그럼 3번째 3을..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 정렬 후 도저히 O(N)으로 처리할 방법이 생각이 나지 않아 풀이를 봤다. (후... 이걸 도대체 어떻게 처음부터 생각하는지 ㅠ) 풀이 방식은 다음과 같다. 1. 서류점수를 기준으로 오름차순 한다. 2. 서류점수를 기준으로 오름차순 했기 때문에 서류순위는 보장이 되고 면접순위만 비교하면된다. 3. 비교방식은 첫 기준점을 서류점수 1등의 면접순위로 잡아준다. 4. 반복문을 1번..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 유명한 웰노운 그리디 문제이다. 풀이방법은 굉장히 간단하다. 끝나는 시간을 오름차순으로 정렬해서 빨리끝나는 것들만 계속 선택하면 된다. 단! 시작시간도 고려해야 하기 때문에 끝나는시간을 오름차순으로 정렬하되, 끝나는 시간이 같을 경우 시작시간을 기준으로도 오름차순을 해주어 빨리 시작하는 것을 선택해주게끔 해야한다. * 그이유는... (시작하자 말자 끝나는 회의가 존재하기 때문..

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부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다." 이 지문때문에 난이도가 상승하는데 사실 이지문이 있어도 모든 나무를 한번씩 자르는 것이 최대 이득이다. 왜냐하면 어차피 나무들은 냅두면 계속 자라기 때문에 가장 적게 자라는 나무부터 오름차순으로 계속 베어가면 ..