코딩하기 좋은날

https://www.acmicpc.net/problem/7576 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 익은 토마토가 있을경우 하루뒤 그토마토의 좌우상하의 토마토가 익는 방식으로 하여 모든 토마토가 익는데 까지 걸리는 날을 계산하는 문제입니다. 하루마다 익은 토마토 기준으로 좌우상하의 토마토가 익게되므로 이 문제는 bfs 방식으로 해결을 하였습니다. 저는 우선 토마토 배열에다 토마토 정보를 입력받고 처음 익은 토마토들을 큐에 넣었습니다. 그리고 그토마토들을 하나씩 bfs를 진행하여 주며 처음 0일날 큐의 사이즈를 미리 len 변수에 저장해놓고 0일날 토마토들이 모두 빠져나오면 +1일을 더해주었습니다. 그리고 나서 +1일날의 큐의 사이즈를 또다시 len 변수에 집어넣고 그토마토들에..

https://www.acmicpc.net/problem/1260 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 정점의 개수와 정점들 사이의 간선들을 입력받고(양방향) DFS와 BFS로 탐색하였을 경우의 경로를 각각 출력하는 문제입니다. DFS(깊이 우선 탐색)는 재귀함수를 이용하여 구현하였고, BFS(너비 우선 탐색)는 큐를 이용하여서 구현하였습니다. 정점들 사이의 인접관계를 표시해주는 배열과 정점의 방문 여부를 알기위한 배열이 각각 필요합니다. 다음은 코드입니다. #include #include int adjacent[1002][1002]; //정점들 사이의 인접관계를 표현하기 위한 배열 int visited[1002]; //방문 여부를 알기위한 배열 using namespace st..

https://www.acmicpc.net/problem/10971 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n개의 도시를 입력받고 각각의 도시에서 도시로 이동하는 입력 비용을 입력받은 뒤 모든 도시를 순회하는 가장 작은 비용을 출력하는 문제입니다. visited 배열을 선언해서 각 도시를 방문했는지를 체크하면서 dfs를 이용하면 풀리는 문제입니다. 도시에서 도시로의 비용이 0일때는 이동이 불가능한 것이므로 이동을 못하도록 조건을 넣어주어야 합니다. 외판원 순회는 NP-Hard 문제로써 N이 커지면 엄청난 시간이 걸리는 문제입니다. 따라서 dfs를 이용하면 N!의 시간이 걸리게되어 이문제에선 통과하지만 N이 더커지면 불가능하죠. 실제로 N이 더커지면(약16정도) 비트마스킹+dp로 푸..

https://www.acmicpc.net/problem/1182 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 어떤 원소들을 가지고 있는 집합이 있을 때 그 원소의 부분집합들 중 합이 S가 되는 것의 개수를 찾는 문제입니다. 원소의 개수가 20개 까지이므로 20개 일때의 부분집합의 개수는 2^20-1 입니다. 따라서 brute force로 해결이 가능하므로 저는 그냥 함수를 하나 만들어서 재귀적으로 호출하며 모든 경우를 따지는 방법으로 풀었습니다. 다음은 코드입니다. #include using namespace std; int num; void rec(int *arr,int N, int result, int S, int k) { if(result == S) num++; for(int i..

https://www.acmicpc.net/problem/1747 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 소수이면서 팰린드롬 수인 숫자를 입력받은 수보다 크면서 가장작은 숫자를 출력하는 문제입니다. 입력이 1000000까지 가능하므로 1000000보다 큰 수중에 가장 작은 소수 까지만 구해놓으면 됩니다. 어떤 수인지 몰라서 저는 그냥 2000000까지 구했습니다. 소수는 에라토스테네스의 체로 구해 놓고 팰린드롬 수를 판별하여야 하는데 저는 먼저 소수인 수를 10으로 나눠주면서 자리수별로 벡터에 집어 넣었습니다. 그런다음 벡터의 맨앞과 끝부분을 비교하며 모두 동일하다면 소수이면서 팰린드롬 수 인것으로 판별을 하였습니다. 다음은 코드입니다. #include #include //에라토스..

https://www.acmicpc.net/problem/1644 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 어떤수가 연속된 소수의 합으로 이루어 질 수 있는 경우의 수를 출력하는 문제입니다. 에라토스테네스의 체를 이용하여 소수들을 판별하고 그 소수를 모두 벡터에 집어넣은 뒤 첫번째 소수부터 계속 더해가며 그 숫자가 나오는 배열의 인덱스 값을 증가 시켰습니다. 총 범위가 4000000 이고 소수의 개수가 28만개 정도 나와서 시간초과가 날거 같았는데 합이 4000000을 넘으면 의미가 없어지므로 탈출하는 조건을 넣어 주어서 그런지 통과가 되었습니다. 다음은 코드입니다. #include #include #define MAX 4000001 using namespace std; int ma..

https://www.acmicpc.net/problem/5568 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n개의 카드중 k개를 뽑아서 만들 수 있는 숫자의 개수를 구하는 문제입니다. 저는 이 문제를 findfunc이라는 함수를 만들어 한장씩 뽑아서 재귀호출로 덧붙이는 방법으로 해결을 하였습니다. 벡터를 하나두어 현재 까지 사용한 카드의 인덱스를 1로 바꿔주어 중복으로 사용 할 수 없도록 하면 모든 경우를 구할 수 있습니다. 다음은 코드입니다. #include #include #include using namespace std; string str[11]; set s; vector v; void findfunc(int i,int k, int n, string str2) { if(k ..

https://www.acmicpc.net/problem/2896 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 각 주스의 양과 비율을 입력받고 최대로 만들 수 있는 양을 만든후 남은 양을 출력하는 문제입니다. 3개 주스의 양을 입력받고 각 비율로 나누어서 몫이 가장 작은 주스의 몫을 기준으로 모든 주스를 만들고 남은 양을 출력하면 되는 간단한 문제입니다. 출력값에 소수점 6자리까지 출력이 되어있어서 저는 setprecision(6)을 이용하여 6자리로 출력을 하였습니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); double..