문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍 문제이므로 일단 직관적인 top-down 방식으로 풀어보았다. 메모이제이션을 위한 배열 max_stair[300][2] 선언하는데 2차원으로 선언하는 이유는 해당 위치가 직전 계단과 연속되는지를 저장하기 위해서이다. max_stair[ ][ 0 ] 에는 두 계단을 뛰어 연속되는 계단이 없는 경우를, max_stair[ ][ 1 ] 에는 한 계단만 올라가 이전의 계단과 연속되는 경우를 저장한다...

문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 전형적인 다이나믹 프로그래밍 문제이다. 이런 문제의 특징인 부르트 포스로 모두 계산하기에는 경우의 수가 너무 많다. 이러한 경우의 수들 중 중복계산을 수도 없이 호출하기 때문에 우리는 계산된 값들을 저장하여 최적화를 할 수 있다. 해당 문제에서 모든 집들을 단순히 3가지 색으로 칠하는 경우의 수는 3^1000 이므로 시간 초과가 발생한다. 하지만 메모이제이션으로, 해당 순서의 집..

문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 풀이 해당 문제는 -1,000,000,000 이상 1,000,000,000 이하의 범위를 가지는 선들이 주어진다. 따라서 이를 단순히 20억 개의 배열에 저장해서 표현하기에는 메모리 제한으로 불가능하며 비효율적이다. 이 문제는 스위핑 알고리즘 대표적인 문제로 아래와 같은 방법으로 해결 가능하다. 해당 문제에서 일단 배열 points에 입력을 받고 선의 시작 부분을 기준..

문제 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 행렬 A의 제곱 수인 B는 최대 100,000,000,000의 값을 가지기 때문에 단순히 A를 반복해 곱하는 것은 시간 초과를 발생시킨다. 이와 같이 입력값이 너무 큰 경우 분할 정복을 떠올리자. 제곱 수를 pow_num이라고 하면 pow_num %2 ==1 인 경우, 즉 홀수라면 A^(pow_num-1) * A를 짝수라면 A^(pow_num/2) * A^(pow_num/2) 로 계산한다면 제곱 연산을 O(logB..

문제 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 풀이 간단한 분할 정복 문제. 대체로 분할 정복 문제들은 입력이 굉장히 큰 경우가 많아 브루트 포스로 접근하면 시간 초과가 발생한다. 해당 문제도 최대 3^7의 큰 입력을 받는다. 행렬은 항상 같은 크기인 9개의 종이로 자르기며 재귀호출을 하기 아래와 같은 기저 사례가 필요하다. 기저 사례: 잘라진 크기가 1인 경우 해당 origin_paper[row][col] 값을 바로 반환한다. 위의 기저 ..

문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 처음 문제를 접하면 가장 큰 종이(5x5)부터 순서대로 대입해보면 되는 그리디 알고리즘처럼 느껴진다. 하지만 이러한 방식으로 문제를 해결하면 아래와 같은 예외적인 입력에서는 오답을 출력한다. 위와 같은 종이 판에 5-> 4-> 3-> 2-> 1 의 순서로 종이를 대입하게 되면 위와 같이 3x3 크기의 종이 1개가 먼저 배치된 후 나머지는 1x1 크기의 종이 4개가 채우게 된다...

문제 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 단순한 문제인데 정답 비율이 낮은 이유는 있었다. 일단 풀고 보니 런타임 에러가 나서 계속 string의 범위 값을 확인했지만, 사실은 문서보다 찾는 단어가 더 긴 경우를 예외처리해주지 않으면 문서(document)의 범위 값을 넘어 버려 런타임 에러가 발생한다. 예외처리만 확실하다면 나머지는 간단하다. 처음부터 끝까지 substr() 을 이용하여 찾는 단어(word)와 비교하여 맞다면 count를 1 증..

문제 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 궁수를 배치하는 경우의 수를 모두 탐색하여 해당 배치에서 최대 몇 명의 적을 죽일 수 있는지 확인하여 최댓값을 구하면 되는 부르트 포스 문제이다. 거리가 같다면 왼쪽의 적부터 공격하는 것과 궁수들이 동일한 적을 공격할 수 있다는 것을 주의 하며 구현하자. ArrayArcher(): 3명의 궁수를 배열하는 모든 경우의 수를 탐색. isArcherPosition[]에 해당 궁수가 배치되면 true 값을 저장하여, ..

문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 9,876,543,210로 int형의 최댓값인 2,147,483,647보다 크기 때문에 int 형이 아닌 long형을 써주지 않아 그런것 같다. 본인의 경우에는 감소하는 수가 0~9까지만 이용가능 하므로, 11자리 이상 갈 일이 없다고 생각하질 않고 문제를 풀어 메모리 초과가 발생했다... 두 점만 명심하고 풀면 어렵진 않다...

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 풀이 테트로미노는 문제에서 나오는 5가지의 모형을 대칭, 회전시키면 총 19개의 고정 형태의 테트로미노가 나온다. 종이의 크기는 500이하로, 19가지의 모형을 모두 대입해서 모든 경우의 수를 구하는 게 충분히 가능하다. 이를 구현하기 위해서 (0,0)인 현재 위치로 부터 상대적인 위치를 저장한 int tetrominoModel[19][3][2] 가 필요한다. 1 2 3 4 5 6 7 8 ..