https://www.acmicpc.net/problem/1661 문제 분류를 봐도 아이디어를 떠올리기 힘들었던 문제분류를 보기 전까지는 자연스럽게 그리디가 계속 떠올랐다. 우선 N이 작기때문에 뭔가 다 해보면 될 것 같다는 생각은 든다.그런데 어떻게 다 해봐야할 지 감이 잘 안온다.이 문제를 풀 때는 한번 예제 입력 1번에 해당하는 케이스를 다 써보면 풀이를 떠올릴 수 있다. 예제 입력에 1번에 있는 물건 3개에 대해서 각각을 사는지 안사는지 경우의 수를 모두 따지면 이렇게 8가지가 나온다.이를 직접 손으로 다 쓰다보면 규칙이 보인다. 어쨌든 할인율은 결국 1, 2, 3 프로중 하나밖에 없다.그리고 최종 할인되는 가격은 어떤 물건을 먼저 사느냐에 상관없이 항상 기존 가격 * 각각의 할인율들의 곱으로 표..
https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net BFS 를 활용하는 시뮬레이션 문제이다. 구현할 때 모든 조건을 꼼꼼히 살펴야하고, 작은 사소한 실수 하나로도 문제를 틀리기 때문에 난이도가 높다. N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] score = 0 while True: x, y, size = find_block..
https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 개수와 각 추의 무게가 주어졌을 때, 주어진 추들을 양팔 저울에 올려 측정할 수 있는 무게의 종류를 구하는 문제이다. 추를 양팔 저울의 한 쪽에만 올리는 경우와 다른 반대쪽에도 올릴 수 있는 경우가 있다는 점이 이 문제의 어려운 점이다. 측정하려는 무게를 x, 현재 사용하는 추의 무게를 w, 이전까지 측정한 적 있던 무게를 p 라고 하자. 그렇다면 측정하려는 무게를 양팔저울의 왼쪽에 놓았을 때..
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 한 노드에 대한 최단 경로에 특정 경로가 포함되어 있는지를 확인하는 문제이다. 아이디어는 어렵지 않은데, 구현이 복잡하다. 나는 처음에 다익스트라를 한번 돌리면서, 그 과정에 간선이 포함되는지를 체크하려고 하였다. 그런데 최단경로가 여러개인 경우, 간선이 포함된 최단 경로를 먼저 고르는 것을 구현하기가 어려워서 이 방법은 포기했다. (나중에 난이도 기여 내역을 보니 이렇게 푼 사람도 있었다...
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net class5 문제를 풀면서 만났던 생 수학 문제. 두 정수가 주어질 때, 두 정수를 포함하는 범위의 모든 정수를 이진수로 변환했을 경우 1의 개수를 모두 세는 문제이다. 곧이곧대로 구하면 수의 범위가 커서 시간초과를 받는다. 나는 다음과 같은 풀이를 떠올렸다. 1. 누적합 [a, b] 구간의 모든 정수의 이진수의 1의 개수를 직접 구하기보다 [1, a] 구간의 이진수의 1..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 이 문제는 겉보기에는 단순한 구현 / 시뮬레이션 문제이다. 상어 이동을 구현하고, 낚시만 하면 되는데, 이 상어 이동이 생각보다 까다롭다. 이동하다가 만나면 잡아먹는다는 점에서 구현하면서 윷놀이 문제 생각이 났다. 상어가 만나면 서로 잡아먹는다는 부분, 가장자리에 닿으면 방향이 반대로 바뀌는 부분을 구현하는게 힘들었다. 내가 이 문제를 풀면서 실수한 부분은 2가지였다. 1. 한..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 같은 부분 문자열이 2개 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 문제이다. 나는 골드 3의 티어로 난이도를 낮게 매겼다. 나는 신촌 연합 알고리즘 캠프에서 배운 라빈 카프 알고리즘에 이분탐색을 더하여 풀었다. 이분탐색을 사용한 이유는 다음과 같다. 부분문자열의 길이가 n일 때 문제 조건을 만족한다면 이 해당 부분문자열의 부분문자열도 문제의 조건을 만..
https://www.acmicpc.net/problem/23059 23059번: 리그 오브 레게노 첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구 www.acmicpc.net 1. 아이템의 일부 구매 순서로 전체 구매 순서를 찾는다 => 위상정렬 2. 이때, 구매 과정이 현재 구매가능한 아이템을 모두 "찾기만 하고" 그 결과를 이름 순대로 구매한다. 이 점만 주의하면 된다. 나는 아이템은 맵으로 관리하고 우선순위큐와 위상정렬을 섞어서 풀었다. 맵에 저장한 아이템에 대해 위상정렬 한다. 현재 살 수 있는 아이템 리스트를 만든다. 만들면..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임의 타일 이동을 구현하는 문제이다. 최대 이동 횟수가 5회로 매우 작은데, 한번에 이동에서 선택할 수 있는 경우의 수가 '상하좌우' 4가지 이므로 모든 경우의 수가 4^5 = 1024 이다. 모든 경우의 수를 저장하기 위해서 각 경우마다 최대 20*20 사이즈 판을 순회해야 하므로 한 경우의 수당 연산횟수는 400이다. 1024 * 400 은 굳이 계산해보..
