#INFO 난이도 : GOLD5 출처 : 2170번: 선 긋기 (acmicpc.net) 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x > n; vector line; for (int i = 0 ; i > start >> end; line.push_back(make_pair(start, ..
#INFO 난이도 : SILVER4 알고리즘 유형 : STACK 출처 : 3986번: 좋은 단어 (acmicpc.net) 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net #SOLVE 스택 자료구조를 이용하면 간단하게 풀이 가능한 문제이다. 스택에 문자를 순차적으로 PUSH 하면서 겹치는 알파벳이 있으면 스택에서 POP 하면 된다. ABBA 같은 '좋은 단어'는 스택이 모두 비어질 것이고, ABAB 같은 '나쁜 단어'는 스택에 문자가 남아 있을 것이다. #CODE #include #include #include using..
#INFO 난이도 : SILVER5 알고리즘 유형 : BruteForce 출처 : 1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #SOLVE 모든 경우의 수를 대입하는 브루트포스 알고리즘을 이용해 문제를 풀이하였습니다. 우선, 맨 앞이 검정으로 시작하는 8 x 8 타일 black_board와 하얀색으로 시작하는 8 x 8 타일 white_board 를 string 배열을 이용해 선언해 줍니다. string black_board[8] = { "B..
#INFO 난이도 : SILVER3 알고리즘 유형 : DP 출처 : 1904번: 01타일 (acmicpc.net) 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net #SOLVE DP를 이용해 문제를 풀이하였습니다. 문제의 핵심은 타일의 마지막 수가 0으로 끝나는지 1로 끝나는지에 따라 케이스를 구분해 점화식을 세우는 것입니다. 마지막 수가 1로 끝나는 타일들은 DP[i-1] 값의 타일들에서 오른쪽에 1타일을 추가한 것이고, 마지막 수가 0으로 끝나는 타일들은 DP[i-2] 값의 타일들에서 오른쪽에 00타일을 추가한 ..
#INFO 난이도 : SILVER3 문제유형 : DP 출처 : 9461번: 파도반 수열 (acmicpc.net) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net #SOLVE 규칙을 찾아내 점화식으로 표현하면 되는 간단한 DP 문제 였습니다. DP[1] ~ DP[10] 까지의 값은 직접 초기화해 주었고, DP[11] (N>=11) 부터는 점화식으로 표현했습니다. 단, 조심해야할 부분이 있는데, dp 배열의 자료형을 long long 형으로 초기화 해 주어야 한다는 것입니다. 피보나치의 특성상 수의 값이 매우 큰 폭으..