목록PS (182)
득이공간
[백준 C++] 13172 Σ - 정수론
13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net #include #include using namespace std; typedef long long ll; const ll Mod = 1000000007; ll Pow(ll X, ll Y) { if (Y == 1) { return X; } if (Y % 2 == 1) { return X * Pow(X, Y - 1) % Mod; } ll Z = Pow(X, Y / 2); return Z * Z % Mod; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ..
[백준 C++] 12851 숨바꼭질 2 - 너비우선탐색
12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #include #include using namespace std; int Time[100001]; int Count[100001]; bool Visited[100001]; queue SQ; void NeighborCheck(int Neighbor, int Current) { if (Neighbor 100000) { return; } int CurTime = Time[Neighbor]; int..
[백준 C++] 11054 가장 긴 바이토닉 부분 수열 - 다이나믹프로그래밍
11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net #include using namespace std; int Sequence[1000]; int LengthL[1000]; int LengthR[1000]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i > Sequence[i]; for (int j = 0; j < i; ++j) { if (Sequence[j..
[백준 C++] 9935 문자열 폭발 - 문자열
9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net #include #include using namespace std; string Str; string Bomb; string Current; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> Str >> Bomb; int Length = Bomb.size(); for (int i = 0; i < Str.size(); ++i) { Current...
[백준 C++] 9663 N-Queen - 백트래킹
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;..
[백준 C++] 2448 별 찍기 - 11 - 재귀
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]..
[백준 C++] 31498 장난을 잘 치는 토카 양 - 이분탐색
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..
[백준 C++] 1987 알파벳 - 백트래킹
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..
[백준 C++] 1967 트리의 지름 - 깊이우선탐색
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..
[백준 C++] 1504 특정한 최단 경로 - 다익스트라
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..