ps (6) 썸네일형 리스트형 [백준 16236] 아기상어 C++ # 문제링크 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS로 같은 거리를 탐색합니다. 탐색하다가 먹을 수 있는 물고기가 나오면 vector 에 넣어뒀다가, 같은 거리탐색이 끝나면 vector 중에서 물고기를 골라서 먹고, 아기상어 위치를 해당 물고기 위치로 옮겨서 다시 탐색을 시작합니다. # 제출 코드 #include #include #include #include #include #include using namespace std; stru.. [백준 10835] 카드게임 DFS, DP 풀이.. # 문제링크 www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net DFS 로 모든 경우의 수를 돌려보려고 했는데, 시간 초과가 나서 DP로 풀었습니다. # 제출 코드 // DFS #include using namespace std; int N; int left_card[2000]; int right_card[2000]; void Input() { cin >> N; for (int i = 0; i > left_c.. [백준 7576] 토마토 # 문제 링크 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 쉽게 생각했다가 엄청 고생한 문제다. 1로 표시된 익은 토마토부터 최단거리 구하는거니까 BFS 로 구하면 되겠네~ 했다. 그래서 배열을 입력 받은 후 for 문 돌려가며 1을 찾아서 DFS를 돌렸고, 가장 작은 수로 배열을 채웠다. 테스트 케이스를 돌렸을 때는 다 맞았는데, 제출을 하면 계속 틀렸다고 나왔다. 뭐가 틀린지도 모르고 계속 싸매다가 결국 구글링을 했다. 바로 속이 싸악.. [백준 15650] N과 M (2) #조합 # 문제 링크 www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열을 출력하는 문제로, 조합 문제입니다. 이전 글인 순열 계산 문제에서 4개 중에 2개를 꼽으면 아래와 같습니다. (순열 계산 참고) 2021.03.13 - [Computer Science&Engineering/코딩테스트] - [백준 15649] N과 M (1)) 4 2 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4.. [백준 15649] N과 M (1) # 문제링크 www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제 역시 순열을 출력하는 문제입니다. 이전에 풀었던 순열 문제를 아주 살짝! 수정해주면 풀이를 할 수 있습니다. 아래 "모든 순열" 글을 참고하세요. 2021.03.13 - [Computer Science&Engineering/코딩테스트] - [백준 10974] 모든 순열 # 제출 코드 // N과 M(1) # include using namespace std; int N, M; bool ch.. [백준 10974] 모든 순열 # 문제 링크 www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 순열 출력 구현에 애를 먹었지만, 코드를 보고나서 충격을 받아 외워버렸습니다. 1부터 N까지 DFS를 호출하는데, 출력시에 숫자를 중복해서 넣지 않도록 check 배열을 만들어서 확인해줍니다. 이후 출력을 한 뒤에는 다시 해당 숫자를 쓸 수 있도록 check를 초기화해줍니다. # 제출 코드 # include using namespace std; int N; bool check[10]; int num[10]; void DFS(int node){ if (node >= N) { fo.. 이전 1 다음
