득이공간

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include using namespace std; int N, Cnt; int Col[14]; bool Check(int Index) { for (int i = 0; i < Index; ++i) { if (Col[i] == Col[Index] || abs(Col[Index] - Col[i]) == Index - i) { return false; } } return true; } void DFS(int Index) { if (Index == N) { ++Cnt; return;..

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net #include using namespace std; char Board[3072][6143]; void DrawTriangle(int N, int Row, int Col) { if (N == 3) { for (int i = 0; i < N; ++i) { Board[Row + i][Col - i] = '*'; Board[Row + i][Col + i] = '*'; } for (int i = 0; i < 2; ++i) { Board[Row + N - 1][Col - i] = '*'; Board[Row + N - 1]..

31498번: 장난을 잘 치는 토카 양 장난기 많은 도발꾼 토카는 오늘도 친구인 돌돌이를 도발하고 말았다. 돌돌이는 도발에 넘어갔고, 죽일 듯이 토카를 쫓아오기 시작했다! 토카는 돌돌이로부터 무사히 도망치기 위해 집까지 돌 www.acmicpc.net #include #include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll A, B, C, D, K; cin >> A >> B >> C >> D >> K; ll End = ceil(double(A + C) / D); ll S = 1; ll E = End; ll Catch = En..

1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net #include using namespace std; int R, C; char Map[20][20]; char Alphabet[26]; bool Check[26]; int Max = 0; void DFS(int Step, int Row, int Col) { char Alpha = Map[Row][Col]; if (Check[int(Alpha - 'A')]) { return; } Alphabet[Step] = Alpha; Check[int(Alpha..

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include #include using namespace std; int Max = 0, A = 1, B = 1; list Neighbors[10001]; bool Visited[10001]; void DFS(bool bACheck, int Current, int Length) { Visited[Current] = true; int Cnt = 0; for (const pair& N : Neighbors[Current]) { int Neig..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net #include #include #include #include using namespace std; const int Infinite = INT_MAX; typedef pair node; int N, E; list Neighbors[801]; int Distance[801]; priority_queue SQ; int Dijkstra(int Start, int End) { for (int i = 1; i Distanc..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net #include #include using namespace std; vector DP; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; DP.reserve(N); int Num; cin >> Num; DP.emplace_back(Num); int Max = Num; for (int i = 1; i > Num; Num =..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net #include #include using namespace std; bool TFriend[51]; int Root[51]; int PartyPrimary[51]; int Find(int Node) { if (Node == Root[Node]) { return Node; } return Root[Node] = Find(Root[Node]); } void Union(int NodeA, int NodeB) { int A = Find(NodeA); int B = Find(No..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net #include using namespace std; int House[16][16]; int DP[16][16][3]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > House[i][j]; } }..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int N, M; bool Visit[8]; int Seq[8]; void Print() { for (int i = 0; i M; DFS(0); } DFS & 백트래킹 문제입니다. 중복없이 M개를 고른 수열을 출력해야하기 때문에 방문 체크 배열을 따로 관리하면서 각 경우를 탐색하도록 했습니다.