[백준] 2873번 - 롤러코스터 풀이 시간: 6~7 시간 1) 문제 해결 아이디어 아이디어를 떠올리는데 어려움을 겪은 문제다. 케이스를 분류하고 일반화하기가 까다로운 문제로 지금까지 풀었던 그리디 문제 중에는 제일 어려운 문제인 것 같다. 특히나 r, c가 모두 짝수인 경우가 구현하기 가장 까다롭기 때문에 푸는데 실패를 계속 겪고 정답이 되기까지 시간이 오래걸렸다. 각 칸은 한 번만 방문할 수 있고 지나간 칸의 합이 가장 최대가 되는경로를 출력하는 문제다. 지나간 칸의 합이 가장 최대가 되기 위해서는 최대한 많은 칸을 지나가야한다. 이 문제는 r, c가 짝수인지 홀수인지에 따라서 케이스를 분리하는 것이 중요 포인트다. 3번째 케이스같은 경우는 제외할 1칸을 어떻게 설정할지를 떠올리는 것이 중요하다. 그..
[백준] 12845번 - 모두의 마블 풀이 시간: 30~35분 이내 (풀이1) 문제 그대로 구현한 방법 1) 문제 해결 아이디어 아이디어를 떠올리는 것은 어렵지 않았으나 계속 런타임 에러(TypeError)가 났다. 주어진 테스트 케이스에서는 값이 잘 나왔으나 다른 테스트 케이스의 경우 제대로 된 값이 오류가 발생했다. 1. 두 카드는 인접한 카드 2. 합성한 카드 A의 레벨은 변하지 않음 카드를 합성할 때마다 카드A, B 레벨의 합만큼 골드를 받음 1. 레벨의 최댓값(max)를 기준으로 계속 오른쪽으로 합성하기(최댓값의 인덱스가 맨 마지막이 될 때까지) 2. 최댓값(max)기준으로 계속 왼쪽으로 합성하기(남은 카드가 1개가 될 때까지) 첫번째 오류. 리스트 값 삭제 후 리스트 길이에 대한 처리 리스트 ..
[백준] 11256번 - 사탕 풀이 시간: 10~15분 이내 1) 문제 해결 아이디어 문제 설명대로 코드를 구현하기만 하면 풀 수 있는 쉬운 문제였다. 박스 크기(r, c)에 담을 수 있는 최대 사탕 개수는 (r * c)이다. 최소한의 상자 개수는 박스 부피(volume)가 큰 상자부터 사탕을 담는 것이다. 그래서 입력받은 상자(box)들을 부피 기준으로 내림차순 정렬해주었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for i in range(t): j, n = map(int,input().split()) # 사탕 개수, 상자 개수 box = [] # n개의 박스 크기 res = 0 # 박스 개수 for _ in range(n): box.append(list(map(int, i..
[백준] 16435번 - 스네이크버드 풀이 시간: 10분 이내 1) 문제 해결 아이디어 문제에 나온대로 구현만 하면 되는 쉽게 풀 수 있는 문제다. 높이가 작은 것부터 검사해야 많은 과일을 먹어 길이가 최대가 될 수 있으므로 과일 높이(h)를 오름차순 정렬한다. for문에서 과일 높이가 스네이크 버드 길이보다 커지면 더이상 과일을 먹을 수 없기 때문에 break로 탈출한다. 이미 앞에서 오름차순 정렬이 된 상태이기 때문에 뒤에 값은 더 검사해볼 필요도 없다. 2) 소스코드 n, l = map(int, input().split()) # 과일 개수, 초기 길이 h = list(map(int, input().split())) # 과일 높이(n개) h.sort() # 과일높이 오름차순 정렬 length = l ..
[백준] 1744번 - 수 묶기 (풀이1) 양수, 음수 리스트로 입력받아 계산하기 1) 문제 해결 아이디어 여기서는 처음부터 양수, 음수 2개의 리스트로 나누어 입력을 받고 이후에 계산을 하는 방식이다. 아이디어는 쉽게 떠올렸으나 주어진 테스트 케이스에서는 결과값이 제대로 나왔으나 나머지 테스트 케이스에 대해 오답이 나와 설계 오류를 찾는데 시간이 조금 걸렸다. 여기서 묶는 다는 것은 두 값을 곱한다는 뜻이고 묶지 않는다는 것은 두 값을 더한다는 뜻이다. 1. 양수끼리 묶기(양수는 내림차순 정렬하여 순서대로 양수끼리 곱셈) 2. 음수끼리 묶기(음수는 오름차순 정렬하여 순서대로 음수끼리 곱셈) 3. 0은 음수와 묶기(0은 음수와 곱셈) 4. 양수, 음수 묶지 않기(양수와 음수는 덧셈) 첫번째 오류. 1에 ..
[백준] 1700번 - 멀티탭 스케줄링 (풀이1) 실패 코드 1) 문제 해결 아이디어 첫번째 오류. if문 검사 순서 문제 1. 멀티탭에 빈 구멍이 있을 경우 코드 2. 멀티탭에 현재 플러그가 있는 경우 코드 이런 순서로 검사를 하면 잘못된 코드가 된다. 예를 들어, 입력이 아래과 같다고 하면 2 7 2 2 2 3 1 2 7 1번 조건을 먼저 검사하게 되면 [2, 2] 이런식으로 같은 숫자가 중복으로 들어가게 되는 문제가 있을 수 있다. if문에서는 검사할 조건 순서를 신중하게 설정하자!!!!! 두번째 오류. order 슬라이싱 인덱스 문제 처음엔 현재 플러그(pivot) 기준으로 뒤 순서에 있는 플러그들에 대해서만 검사하도록 order[i+1: ] 으로 코드를 짰는데, 런타임 에러가 났다. 생각해보니 ..
[백준] 2847번 - 게임을 만든 동준이 (풀이1) for문, while문을 다 쓰는 방법 1) 문제 해결 아이디어 아이디어는 쉽게 떠올릴 수 있었다. 이 문제의 핵심은 높은 레벨의 점수가 낮은 레벨의 점수보다 항상 높아야 한다는 것이다. 낮은 레벨부터 차례대로 점수가 입력되었기 때문에 검사는 높은 레벨부터 해야한다. 역순으로 검사를 해야하므로 인덱스 처리를 쉽게하기 위해 해당 리스트(score)을 뒤집는다. 현재 값이 이전 값보다 크다면 점수가 잘못된 것이므로 점수(socre[i])를 1 감소 시키고 감소횟수(cnt)를 1 증가한다. 2) 소스코드 n = int(input()) # 레벨 수 score = [int(input()) for _ in range(n)] # 레벨 클리어 점수 score.rev..
[백준] 1449번 - 수리공 항승 1) 문제 해결 아이디어 아이디어는 쉽게 떠올릴 수 있는 문제였다. 물이 새는 곳의 위치 기준 좌우 0.5 길이 즉, 테이프 길이 1인 테이프 1개로 막을 수 있다. 좌우 0.5이지만 편의상 새는 곳 위치 기준 우측으로 길이 1만큼 막는다고 풀어도 같은 결과가 나온다. 먼저, 새는 곳 위치(loc)를 올림차순 정렬한다. (왼쪽부터 새는 곳을 차례로 막기 위함) 첫번째 새는 곳은 무조건 새로운 테이프를 써서 막아야 하기 때문에 테이프 수(cnt)를 1로 초기화 하고 테이프 끝 지점(tape_end)를 새는 곳 위치(loc[0]) 에서 테이프 길이(l)만큼 더한 값으로 초기화 한다. 나머지 새는 곳의 위치에 대하여 for문을 돌린다. 현재 새는 곳 위치의 끝지점이 최근 붙..
