![]()
문제 풀이 3*N의 2차원 배열을 선언하였고, 각각의 행은 R, G, B를 나타낸다. i번째의 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다는 조건은 결국 연속한 세 집의 색이 같으면 안된다는 조건과 같다. dp[0][i] 행을 예시로 설명하면, i번째에 들어갈 최솟값은 [현재 집을 빨간색으로 칠하는 비용 + (이전 집을 초록색으로 칠하는데까지 필요한 비용, 이전 집을 파란색으로 칠하는데까지 필요한 비용, 이전 집을 빨간색으로 칠하는데까지 필요한 비용 중 최솟값)] 이다. 그런데 이전 집을 빨간색으로 칠하는데까지 필요한 비용엔 연속한 두 집을 빨간색으로 칠하는게 포함되어 연속한 세 집을 빨간색으로 칠하게 되버리니, 수정이 필요하였다. 전전 집을 빨간색으로 칠하는데까지 필요한 비용 + (이전 ..
![]()
풀이 dp배열 초기화한다. 2번 집부터 N번 집까지 순서대로 각 집을 빨강, 초록, 파랑으로 칠하는데 드는 최솟값을 계산하여 DP 배열에 저장한다. 각 집을 칠할 때, 이전 집과 색이 겹치지 않도록 하며 최솟값을 선택한다. 모든 집을 칠하는 비용의 최솟값은 DP 배열의 마지막 행에서 가장 작은 값이다. 코드 #include #include #include using namespace std; int main() { int N; cin >> N; vector cost(N, vector(3)); for (int i = 0; i > cost[i][0] >> cost[i][1] >> cost[i][2]; } vector dp(N, vector(3)); // 초기값 설정 dp[0][..
![]()
https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net # 문제 설명 - 타일 장식물에서, {1,1,2,3,5,8...}과 같이 정사각형 타일 한 변의 길이를 구할 수 있다. - 타일의 개수 N(1 n; dp[1] = 1; dp[2] = 1; for (int i = 3; i
![]()
https://www.acmicpc.net/problem/7510 7510번: 고급 수학 준규는 집을 짓고 있다. 준규는 모든 벽 모양을 직각 삼각형으로 만들려고 한다. 적절히 나무를 잘라 삼각형을 만들었지만, 준규는 각도를 측정할 수 있는 도구를 가지고 있지 않다. 어쩔 수 없 www.acmicpc.net 문제 분석 분류 수학, 기하학, 피타고라스 정리 문제 설명 준규는 집을 짓고 있다. 준규는 모든 벽 모양을 직각 삼각형으로 만들려고 한다. 적절히 나무를 잘라 삼각형을 만들었지만, 준규는 각도를 측정할 수 있는 도구를 가지고 있지 않다. 어쩔 수 없이 줄자를 이용해 삼각형 세 변의 길이를 측정한 다음, 직각 삼각형인지 아닌지를 알아보려고 한다. 삼각형 세 변의 길이가 주어졌을 때, 직각 삼각형인지 아..
![]()
https://www.acmicpc.net/problem/2947 2947번: 나무 조각 첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다. www.acmicpc.net 문제 분석 분류 구현, 시뮬레이션 문제 설명 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다. 동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위..
![]()
문제 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄..
![]()
https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 난이도 골드 3 분류 LCS, DP 들어가기 전에 앞서 LCS 문제들을 풀고오지 않았다면 더 어려울 수 있다. 문제 문제 풀이 풀이 기존 LCS코드에(2중 for문)에 한 줄을 더 늘려주면 된다. 그렇게 되면 3개가 같을 경우 +1이 되므로 사실 2개일 때랑 별 차이가 없는 문제이다. (4개라면 4중, 5개라면 5중으로 굴려주면 될 것이다. 시간복잡도가 N^5인 것만 감안하면..!) 소스코드 def ..
![]()
문제링크 https://www.acmicpc.net/problem/2511 2511번: 카드놀이 첫 번째 줄에는 게임이 끝난 후, A와 B가 받은 총 승점을 순서대로 빈칸을 사이에 두고 출력한다. 두 번째 줄에는 이긴 사람이 A인지 B인지 결정해서, 이긴 사람을 문자 A 또는 B로 출력한다. 만약 www.acmicpc.net 문제 코드 코드설명 A 와 B에 각각 변수값을 넣어주고 카드의 숫자가 큰 사람의 이름을 LastWinner라는 변수에 저장하였다. 이후 반복문을 사용하여 카드를 한장씩 비교하였다. 숫자가 더 큰 사람에게 승점 3점을, 비기면 모두에게 1점을 주는 코드를 작성하였다. 게임이 끝난 후 A,B의 점수가 같다면 LastWinner를 출력한다. LastWinner가 빈다면 모든 라운드가 비긴..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍 문제이며, 이 유형의 문제를 해결하기 위해선 점화식을 잘 세워야 한다. 이 문제에서는 항상 세로의 길이가 2로 고정되어 있으므로, 가로의 길이가 1씩 늘어남에 따른 경우의 수의 증가에 주목하면 된다. 각 경우마다 가능한 타일링의 수를 직접 구하다 보니 규칙이 보였다. dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8... 블록은 가로로만 증가하기 때문에 n개의 타일링은 n보다 작은 부분..
https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제풀이 피보나치 수열은 다음과 같이 수식으로 표현하면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 주어진 문제에서 n의 범위는 0 ≤ n ≤ 1,000,000이다. n의 범위가 크므로, n번째 피보나치 수를 구하기 위하여 재귀함수가 아닌 다이나믹 프로그래밍으로 접근하였다. n번째 피보나치 수를 1,00..
![]()
문제 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 풀이 다이나믹 프로그래밍으로 풀이 편하게 작성하기 위해 N+1행 M+1열인 0으로 이루어진 2차원 리스트 생성한다. 이중 반복문을 통해 1,1부터 N,M까지 dp에 값(해당 위치까지의 최댓값)을 넣어준다. (NXM을 입력받았으므로 [i-1][j-1]에 해당하는 값에 dp로 구한 위쪽[i-1][j]과 왼쪽[i][j-1] 중 큰 값을 더한다.) 최댓값인 오른쪽 아래의 값을 ..
![]()
문제 https://www.acmicpc.net/problem/11068 11068번: 회문인 수 어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력 www.acmicpc.net 알고리즘 분류 수학 브루트포스 알고리즘 문제 어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B..
