분류 전체보기

https://www.acmicpc.net/problem/18114    #문제 간단 정리 투 포인터로 풀었다  #문제 해결 방법  1개로 되는지 확인하고2개로되는지확인3개로되는지 확인한다 2개로 되는지 확인하는 경우는 전형적인 투포인터로 사용하고 3개로되는경우는i번째 를 선택한 다음에다른 2개를 투포인터로 조건에 맞도록 탐색한다 #전체 코드#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, C; cin >> N >> C; vector vec(N); for (int i = 0; i > vec[i]; sort(vec.begin(), vec.end())..

https://www.acmicpc.net/problem/12924  #문제 간단 정리 문자열을 사용한 구현문제정도 #문제 해결 방법 다른사람들은 어떻게 풀었을지 모르겠지만 일단 문제에서 주어진거처럼 뒤에서 1~ 문자열 길이 만큼 잘라서앞으로 붙여서 B 보다 작다면 ok 라는 방식으로 직관적으로 구현햇다 대략 길이가 7자리수니까 주어진 범위가 이백만 정도니까 이백만 x 7 해도 문제가 없음을 알 수 있다.  #전체 코드#include #include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string sA, sB; cin >> s..

https://www.acmicpc.net/proble  #문제 간단 정리 xor 비트연산과 집합과 맵을 잘 사용하자  #문제 해결 방법 우선 이 특정 더하기 접근법을 생각해보면 10 01 일때 1이되고00일때 0 이 되기 때문에 xor 연산과 같다는 걸 알 수 있다 또한 xor 연산을x와 해주게 되면 현재 숫자와 xor연산을해서 x가 나오는 숫자를 알 수 있는데 숫자는 1~9까지 밖에 없기 때문에이 숫자가 전체 몇개가 나오는지 맵으로 카운팅 해주고 각 주어진 숫자를 순회하면서 이 x가 되는 숫자를 확인해서배열에 얼마나 이 숫자가 들어있는지 확인해주면 만족하는 쌍이 몇개인지 알 수 있다. 그리고 물론 중복되는 값이 있으니 이를 후처리 해줄 필요도 있다.   #전체 코드 #include #include #..

https://www.acmicpc.net/problem/11815  #문제 간단 정리 수학과 관찰이 필요한문제 #문제 해결 방법 우선 약수의개수가 홀수이려면 완전제곱수여야 한다 (어떤 수의 제곱이 되는 수 ) 완전제곱수를 쉽게 확인하는 방법은루트를 씌었다가 다시 제곱을해서 원래의 수가 되는지 확인 하는 것  문제에서 X의 최대값이 10^18 이기 때문에 뭐 대략 long double 사용하면 18자리정도 유효숫자를 표현할 수 있는데 10^18 에 루트를 씌우면 10^9 이기 때문에 충분히 표현 가능하다 그래서 루트X가 정수인지는 판단에 문제가 없다 만약 이렇게 풀지 않는다면 이진탐색을 사용하면 되긴 할거다   #전체 코드#include using namespace std;int main() { i..

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 =..