목록Algorithm/백준 (39)
서의 공간
[문제]: 7576번: 토마토 (acmicpc.net) 익은 토마토는 여러 곳에 동시에 있을 수 있다. 기억해야 할 것은 시작점이 여러 개인 BFS는 그냥 모든 시작점을 큐에 넣고 BFS 돌리면 끝이다. 방문 되었는지의 여부를 나타내는 배열이 아닌 거리(몇일 걸렸는지 나타내는 시간)를 의미하는 days배열임을 주의 할 것. 깊이가 1 증가할 때마다 days도 1씩 증가한다. #include #include #include using namespace std; int board[1002][1002]; int days[1002][1002]; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, -1, 0, 1 }; int M, N; int main() { ios_base::syn..
[문제]: 1926번: 그림 (acmicpc.net) 그림의 좌상단에서부터 시작하여 1을 갖고, 방문한 적이 없는 모든 원소에 대해 BFS하면 끝난다. BFS의 기본적인 틀만 기억한다면 쉽게 이해 할 수 있다. area를 계산하는 위치도 눈여겨 보자. if문 바로 안에서 area 변수의 초깃값을 1로 주고 while()문 안에 있는 for()문 안에서 모든 if문을 건너뛰고 vis[nx][ny] = 1; 위 또는 아래줄에 ++area; 해주어도 된다. 다만 시간이 쬐금 더 소모된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nul..
실제 팩토리얼 값을 구할 필요없다. 팩토리얼의 정의를 보면 \[n! = n\times(n-1)\times(n-2)\times\cdots\times 2\times1\] (예) \[10! = 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\] 문제는 일의 자릿수부터 시작해서 처음으로 0이 안나오는 자릿수까지의 0의 개수를 구하는 것이고, 위 식에서 두 수를 곱해서 10이 나오려면 \(10\times 1\)또는 \(5\times 2\)이다. 그러면 결국 나머지 숫자들의 곱에(마지막 자리가 결코 0이 되지 않는다) 100을 곱한 꼴이 되어 0의 개수는 2개다. 이런 식으로 생각하다 보면 0이 추가되는 규칙이 발견되는데, 125..
[문제]: 10826번: 피보나치 수 4 (acmicpc.net) BigInteger 클래스를 만들어서도 풀어보자. operator+()함수의 string 파라미터는 참조형 변수가 아니다. #include #include #include #include using namespace std; // 이 함수는 46번 라인에서 호출됨 string operator+(string str1, string str2) { string ret; int n = 0, carry = 0; // 일의 자리부터 계산하기 위해 reverse(begin(str1), end(str1)); reverse(begin(str2), end(str2)); // 자릿수가 더 적은 숫자 앞에 0을 채워준다. // 예) 254 + 31 -> 254..
[문제]: 14501번: 퇴사 (acmicpc.net) 아아아 #include #include #include #include using namespace std; vector TP; vector dp(16, 0); int MaxRevenue(int n) { int result = 0; for (int i = 1; i N; for(int i = 0; i > T >> P; TP.push_back(make_pair(T, P)); } cout
[문제]: 1463번: 1로 만들기 (acmicpc.net) 숫자가 3의 배수 또는 2의 배수라고 바로 3, 2로 나누어서는 안 된다! 먼저 -1을 한 후의 연산 횟수가 더 적어질 수 있기 때문이다. 10을 예를 들어보면, 10은 2의 배수이니 2로 먼저 나눈다고 해보자. 아래 식은 괄호 없이 순서대로 계산한다(사칙연산 계산 순서 무시). 이때 연산 횟수는 총 4회. \(10\div2-1\div2-1=1\) 하지만, 이렇게 계산할 수도 있다. \(10-1\div3\div3=1\) 이때 연산 횟수는 총 3회. 따라서 주어진 숫자가 3의 배수 또는 2의 배수라 하더라도, 나누기하기 전에 먼저 -1을 한 연산 횟수와 비교를 해야 한다. 먼저 -1을 한 연산 횟수보다 작으면 나누기, 아니면 -1부터. 아래 코드..
[문제]: 17626번: Four Squares (acmicpc.net) 예를 하나 가지고 하나하나 따져보자. 첫 for문은 제곱수는 1개의 제곱수로 표현할 수 있으므로 그 부분을 처리한 것이고, 핵심은 2번째 for문이다. 먼저 dp[n]의 정의다. \[dp[n]=\text{제곱수들의 합이 \(n\)인, 제곱수들의 최소 개수}\] 즉, \(1=1^2\text{ 이므로 } dp[1] = 1,\) \(5=1^2+2^2\text{ 이므로 } dp[5] = 2,\) \(13=2^2+2^2+2^2+1^1\text{ 이긴 하지만, } 13=2^2+3^2\text{ 이기도 하다. 최소 개수이어야 하므로 }dp[13] = 2,\) \(60=1^2+1^2+3^2+7^2\text{ 이므로 } dp[60] = 4\) 이다..
[문제]: 9625번: BABBA (acmicpc.net) A와 B의 개수를 세기 위해 pair타입을 이용했다. pair 타입은 (A의 개수, B의 개수) 형식이다. 문자열을 본다면 스위치를 k번 눌렀을 때 문자열은 항상 (k-1번 문자열 + k-2번 문자열)이다. 식으로 표현하면, \[strPush(k) = strPush(k-1)+strPush(k-2)\] (예) 스위치를 5번 누른 문자열 = "BABBABAB" 스위치를 4번 누른 문자열 = "BABBA" 스위치를 3번 누른 문자열 = "BAB" 여기서 오해하지 말아야 할 것은 + 연산이 실제로 더하기를 의미하는 것은 아니고 문자열의 concatenate, 즉 문자열을 연결하는 연산이다. 실제 문제는 문자열이 아닌 A와 B의 개수를 구하는 것이기 때문..