나이트의 이동 문제는 BFS로 최소 이동 수를 찾는 문제이고 이동하는데 걸리는 횟수를 dist에 저장하면서 bfs를 돌리면 간단하게 풀립니다. 풀이 #include using namespace std; int dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2}; int dy[8] = {-2, 2, -1, 1, -2, 2, -1, 1}; // 나이트의 이동 경로 int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, l; cin >> n; //테스트 케이스 입력 while (n--) { cin >> l; queue q; //bfs를 위한 queue int dist[301][301]; //distance를 저장하는 이차원 배열 for (in..
토마토 문제는 대표적인 bfs 거리 구하기 문제의 응용인데 저번 문제로 2차원에서 토마토를 다루었지만 이번에는 3차원에서 토마토로 다루도록 해보겠습니다. 해당 문제를 푸는 데에 핵심적인 개념은 bfs에서 dict라는 array를 통해 거리를 구하는 것에서 단순히 일 수로 바꾸면 되는건데 시작점이 한 개가 아니라 여러개라는 점입니다. 시작점이 여러개라는걸 해결하는 방법도 간단합니다. 시작점들을 미리 큐에 두고 bfs를 돌리면 됩니다. 어차피 최소 일수를 구하는 것이기 때문에 어떠한 시작점에서 방문했다면 다른 시작점에서 방문하지 않을 것이고 큐에서 bfs를 진행하는 과정은 일 수에 따라서 큐에 들어갑니다. 풀이 #include using namespace std; int box[101][101][101]; ..
문제 설명 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 지난 인증시험 이후 충격을 많이 받았기에 차근차근 코딩 문제도 풀어보려고 합니다. solved ac에서 티어를 올릴 생각으로 차근차근 푸는데, 이번 문제는 이진탐색을 사용하지 않으면 시간초과가 뜨는 문제였습니다. 입력받을 선의 갯수를 말하고, 원하는 갯수가 들어오면 그 갯수를 만들 수 있는 최대로 자르는 길이를 출력하는 문제인데 갯수가 몇 개인지는 그냥 입력..
이번 문제는 11690번 LCM(1, 2, ..., n)입니다. 문제는 https://www.acmicpc.net/problem/11690 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 다음과 같습니다. 문제를 해결하기 위해서.. 입력받은 수보다 낮은 소수들의 거듭제곱의 최대들만 곱하면 LCM이 되리라 생각하고 중복을 막고자 마지막에서 여러 쌩쇼를 했고 int 배열의 최대 사이즈가 10^7이기에 입력인 10^8을 커버하고자 vector까지 써봤는데요. 이번에는 메모리 초과로 나타나서 안 되더군요 #include #inc..
이번 문제는 거의 소수라는 문제입니다. 알고리즘적으로는 꽤 간단한 편이지만, 오버플로우를 처리하는 등의 꼼수가 필요한 문제였습니다. DATA 영역과 STACK 영역에 대해서 특성 한 가지를 알게 된 소중한 문제였던 것 같습니다. 범위가 주어지면 해당 범위 내에서 소수의 n제곱이 되는 수들의(n >= 2) 갯수를 찾습니다. 갯수를 찾아서 몇 개가 있는지 출력합니다. 풀이 우선 소수가 뭔지를 알아야겠고, 더군다나 범위로 사용을 하니까 에라토스테네스의 체를 사용합니다. 이 때 배열의 최대 크기는 10^7이라고 합니다. 우리가 입력받는 수의 범위는 1
이번 문제는 음식 평론가라는 문제이다. https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 그냥 소시지가 n개 있을 때, m명의 사람에게 나누어주려면 최소한으로 몇번 잘라야 하는가?에 대한 문제이다. 아무래도 종종 빙고게임 판을 그릴 때(표라던가) 몇 번 잘라야 하는 문제가 떠오르긴 했다. (쓸데없는 말) 계속해서 생각을 해보니까 소시지 n개를 따로 생각할 필요 없이 그냥 길이가 n인 소시지를 m등분 한다고 생각하면 좀 편했다. 그러면 한명이 n/m씩 소시지를 가져야 한다. 그럼 n : 3 m : 4 를 예로 들었을 때, 1명이 가져야 하는 양은 3/..
가로수라는 문제이다. 이 문제를 읽고 생각해보면 가로수 위치와 간격에 대한 것인데, 어떻게든 간격이 작은 것에 맞춰야하고 간격이 2 4 6 처럼(1, 3, 7, 13) 모든 간격의 관계가 서로소가 아니면, 최대공약수의 간격으로 맞추고 그렇지 않으면 그냥 간격을 1로 하여 채워넣어야 한다는 것이다. 그걸 고려하면 코드가 너무나도 금방 짜인다. #include int gcd(int a, int b) { return b? gcd(b, a%b):a; } int main(void) { int i, j; int n; int loc[100000] = {0,}; int gap[100000]; int tmp; scanf("%d",&n); for(i=0; i
이번 문제는 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 최대공약수와 최소공배수를 이용해서 역으로 숫자를 찾는 문제입니다. 처음에는 어떻게 하지..?? 하다가 수학적 지식이 있으면 쉽게 방법을 찾을 수 있었습니다. 풀이 방법 처음에는 최대공약수 g와 최소공배수 l을 보고 l에서 뭔가 약수들을 g로 넘겨주면서 곱하다보면 g*l = a*b가 되는 점을 이용하여 구할 수 있을거 같았는데, 우선 거기서 오버플로우가 일어나기 쉽고 이런 식으로 구하면..
