[백준]/C++

https://www.acmicpc.net/problem/3005 #문제 간단 정리 구현문제에 가깝다 문제에 주어진걸 그대로 구현하자 #문제 해결 방법 생략 #전체 코드#include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int R, C; cin >> R >> C; vector> board(R, vector(C)); // 입력 for (int i = 0; i > board[i][j]; } } vector candidates; for (int i = 0; i = 2) candidates..

https://www.acmicpc.net/problem/3671  #문제 간단 정리 소수판별 + 구현문제 #문제 해결 방법 우선 숫자가 주어지면 이 숫자로 만들수 있는 조합으로만들수 있는 소수이니 숫자로 만드는조합 -> dfs 사용 소수판별 -> 에라토스테네스의 체  이렇게 두가지 구현하면 된다 dfs구현에서 최대길이가 7자리수라 시간복잡도에는 문제 없는 것을 알 수 있다. #전체 코드#include #include #include #include using namespace std;static const int MAX = 10'000'000;bool primeArr[MAX]; set primeSet; string s;set madeNumbers; void sieveOfEratosthen..

https://www.acmicpc.net/problem/32864  #문제 간단 정리분류는 애드혹 + 게임이론으로 되어있는데... 대충 그리디하게 생각해서 풀었다고 생각한다.  #문제 해결 방법 두명다 최선의 방법을 사용하기 때문에 만약 종착역에 도착하기전에 1 (환승역이 있다면) 그 이후에 0(일반역) 에서 멈춰서 승리하려고 하기 때문에 나는 뒤에서부터 역산해서 누가 이기면 되는지 추정하면 된다고 생각해서 뒤에부터 만약 1이 온다면 1뒤에 0이오면 승리자가 그대로고 (01)1뒤에 1이 오게 되더라도 바로 자기턴이 돌아오기때문에 상관없다 (11) 다만 2번째역이 환승역이라면 (index 1)   바로 환승을해야 되기 때문에 기존의 승리자가 바뀌게 된다 뭐 대충 이렇게 시뮬레이션해서 풀었다. #전체 코드..

https://www.acmicpc.net/problem/24508  #문제 간단 정리투 포인터를 사용하자 #문제 해결 방법 일단 정렬을 해주게 되면우측에는 나도리가 많고 좌측에는 적기때문에 조건문1)우측에 나도리가 기준치보다 적다면 좌측의 나도리를 왼쪽의 나도리를 사용해서채워주는게 유리  조건문2)우측의 나도리가 기준치보다 많고좌측의 나도리가 기준치보다 적다면당연히 좌측의 나도리를 사용해서 우측의 나도리를 기준치만큼 채워주면된다   #전체 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, t; cin >> n >> k >..

https://www.acmicpc.net/problem/16970  #문제 간단 정리브루트포스 구현 + gcd #문제 해결 방법두 점을 골라서 gcd로 정수점의 개수들을 계산해주자  #전체 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; int ans = 0; for (int x1 = 0; x1 x2 || (x1 == x2 && y1 > y2)) continue; int dx = x2 - x1; int dy = y..

https://www.acmicpc.net/problem/15559  #문제 간단 정리그래프를 이용한 탐색 문제 #문제 해결 방법 맵을 벗어나지 않는다고 주어져 있으니사이클이 발생할수 밖에 없고 사이클의 개수를 판별해 주면 된다. 끝점 혹은 사이클을 판별하면 되는데dfs 를 사용하지만 중복탐색이 안되도록 주의해야 한다  #전체 코드#include #include #include using namespace std;int n, m;vector> board;vector> state;// state: 0 = not visited, 1 = visiting, 2 = doneint presentCount;int dmap(char dir) { if (dir == 'N') return 0; if (dir =..

https://www.acmicpc.net/problem/4347  #문제 간단 정리 가능한 틱택토 모양인지 판별하라는 문제 #문제 해결 방법 워낙 3x3 이라 작기 때문에브루트포스로 해결하면 된다 x가 이겻는지 o가 이겼는지 확인하고 돌의 개수를 확인하자 #전체 코드 #include #include #include #include using namespace std;int n;bool checkLine(vector>& board, char c) { // c로 이루어진 3연속이 있는지 확인 for (int i = 0; i >& board) { int OCount = 0; int XCount = 0; for (int r = 0; r > n; for (int i = 0; i ..

https://www.acmicpc.net/problem/32823  #문제 간단 정리CCW + 수학 문제 #문제 해결 방법 우선 관찰을 하면 p1 p2 두 점 사이에 선분이홀수개면 둘 다 채굴 불가짝수개면 둘 다 채굴 가능인 것을 알 수 있다. 때문에 두 점 사이에 선분이 몇개가 있는지 확인하면 되는데 CCW 를 활용하기 위해서 각 좌표들을 삼각함수를 사용해 극좌표를 직교좌표로 변경해준다 그런데 tan로 y좌표를 구하면 무한대가 되버리니sin 으로 y좌표를 구해주고 각 선분에 대해서 p1 p2 에 대해서 ccw로 교차 판정을 해주면 된다 삼각함수 변경하는 부분에서 실수 오차가 날수 있으니 주의해 줘야된다.  #전체 코드#include #include #include using namespace std;..

https://www.acmicpc.net/problem/15752  #문제 간단 정리 #문제 해결 방법 이 문제에서 중요한건 그래프 문제로 바꿔서 생각하는 것이다 일단 전달되는 것에서 그래프를 착안 할 수 있는데전달되는걸 간선으로 처리한다고 하면 진입차수가 0인 소들은 농부가 직접 전해줄 수 밖에 없다때문에 그래프 탐색으로 진입차수가 0인 소들의 진입들을 처리해주면 진입차수가 1 이상인 소들이 남아있을텐데진입차수가 1인데 방문이 안됫다는 이유는 서로 거리가 같아서 주고 받기 때문에  노드 A는 노드 B에게 공을 전달하고,노드 B는 노드 A에게 공을 전달합니다.와 같은 상황이 생기기 때문이다 즉 이렇게 진입차수가 1이상인 것들의 방문을 처리하면서 필요한 공 개수를 체크해 주면된다  결론적으로 그래프로 바..

https://www.acmicpc.net/problem/2193  #문제 간단 정리 기본적인 dp 문제  #문제 해결 방법     // 이친수는 1이 두번 나타나지 않음     // dp[i][j] = i길이의 j로 끝나는 이친수 의 개수 =     //dp[i][0] = dp[i-1][0] + dp[i-1][1]      // dp[i][1] = dp[i-1][0]  #전체 코드#include #include #include using namespace std;int main() { long long n; cin >> n; vector> dp(n+1,vector(2)); // 이친수는 1이 두번 나타나지 않음 // dp[i][j] = i길이의 j로 끝나는 이친수 의 ..