[백준 1987] 알파벳 [C]
풀이 입력된 대문자 알파벳의 아스키코드 값을 이용해, 한 번이라도 방문한 적 없는 경우에만 탐색해 최대의 칸 수를 구하면 된다. 소스코드 #include #include char arr[20][20]; bool visited[26]; int R, C, result; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; void BT(int x, int y, int cnt){ cnt > result && (result = cnt); for (int i = 0; i = 0 && ny >= 0 && nx < R && ny < C){ int idx = arr[nx][ny] - 65; if ..
2021. 9. 1.
[백준 11414] LCM [C]
풀이 gcd(x, y) = gcd(x-y, y)임을 이용해 풀이했다. A < B일때, gcd(A+N, B+N) = gcd(A+N, B-A)이므로, B-A의 약수를 이용해야 한다. 1~ B-A범위를 모두 탐색하면 시간초과가 발생하므로 다른 방법을 생각해야된다. 위의 예시에서 알 수 있듯이, 시작값(X)을 기준으로 X+N이 B-A로 나누어 떨어질 때 X~(X+B-A)구간에서 가장 작은 LCM값을 가진다는 점을 알 수 있다. X+N이 B-A로 나누어 떨어진다는 것은, B-A의 약수로도 나누어 떨어지는 것을 의미한다. 따라서, A가 B-A의 약수로 나누어 떨어지지 않을 때, N번째 수를 생성 후 LCM을 계산해 가장 작은 N값을 구하면 된다. 소스코드 #include #define ll long long int..
2021. 8. 31.
