분류 전체보기
-
[1688] 지민이의 테러BOJ 2022. 7. 16. 16:42
https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있 www.acmicpc.net 다각형 밖의 임의의 점 하나를 잡고, 다각형 내에 존재하는지 판단 대상이 되는 점과의 선분을 만든다. 다각형을 구성하는 n개의 선분과 교차하는 횟수가 홀수번이라면 다각형 내의 점이 된다. 다각형의 경계 위에 있는 경우를 위 방식으로 잡아내지 못하므로 별도로 체크하고, 다각형 밖의 임의의 점과 그은 선분이 기존 다각형을 구성하던 선분과 평행하지 않도록 잡았다. #include using n..
-
[14907] 프로젝트 스케줄링BOJ 2022. 7. 4. 05:01
https://www.acmicpc.net/problem/14907 14907번: 프로젝트 스케줄링 입력은 1줄에서 26줄까지 입력될 수 있으며, 각각은 다른 작업 (위 예제에서 말하자면 A, B, C, …) 을 포함한다. 각 줄에는 다음과 같은 내용이 포함된다. 작업 이름을 나타내는 영문 대문자 하나, www.acmicpc.net 입력이 귀찮은 구현(?)문제, 알파벳은 숫자로 바꿔주거나, 배열 크기를 100정도로 잡거나.. 한줄 입력받고 파싱할때, 작업 전 완료해야하는 작업이 0개인 경우에 ' '(공백)이 한줄에 한번만 들어올 수 있음에 유의 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else cons..
-
[2585] 경비행기BOJ 2022. 6. 23. 14:07
https://www.acmicpc.net/problem/2585 2585번: 경비행기 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간 www.acmicpc.net 두 점이 주어질때 필요한 연료를 계산할때, (0, 0), (100, 0)같이 딱 떨어지는 경우를 고려하기 위해 적당히 작은 값을 빼놓고 10으로 나눈 몫을 취했다. 해당 부분을 구현하고 나면 남은것은 방문처리인데, 어떤 정점을 더 적은 횟수로 경유해서 온 경우만 방문하기 위해 int vst[n]; 형태로 선언하여 방문처리 해주었다. #include using namespace std; #ifdef ONLI..
-
[1504] 특정한 최단 경로BOJ 2022. 6. 21. 12:36
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 방문하는 두 정점이 x, y라고 하면, 1 - x - y - n 1 - y - x - n 위 두 가지 경우만 체크하면 된다. x나 y가 1, n인 경우도 나올 수 있지만, 예외처리를 할 필요는 없다. 입력이 연결그래프인지를 먼저 판별하면 -1을 출력해야 하는 경우를 배제하고 시작할수도 있겠다. #include using namespace std; #if..
-
[16168] 퍼레이드BOJ 2022. 5. 22. 03:48
https://www.acmicpc.net/problem/16168 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 연결그래프이면서, 홀수간선을 갖는 정점이 2개 이하인지를 판별해야 한다. bfs로 아무거나 시작점으로 잡아서 v개를 방문했는지를 체크하고, 입력을 인접리스트로 받으면 1&adj[i].size()로 홀수간선을 갖는지를 파악할 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = f..
-
[1199] 오일러 회로BOJ 2022. 5. 22. 03:44
https://www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net 입력은 연결그래프이므로 이쪽은 신경쓰지 않도록 하고, 회로이니 홀수갯수 간선을 갖는 정점이 없어야한다. 이분매칭처럼 작동과정에 비해 코드가 간단하게 구현되는 듯 하다. 아마 DFS를 사용하기 때문이지 싶은데.. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr ..
-
[18005] Even or Odd?BOJ 2022. 5. 20. 15:02
https://www.acmicpc.net/problem/18005 18005번: Even or Odd? Output 2 if the sum of any n consecutive integers in the range from 1 to 1018 must be even, 1 if the sum must be odd, or 0 if the sum could be either even or odd. www.acmicpc.net 1) 1부터 n까지 더한 경우 2) 2부터 n+1까지 더한 경우 위 2가지만 체크하면 된다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local =..
-
[4659] 비밀번호 발음하기BOJ 2022. 5. 14. 14:34
https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 요구사항이 많으므로 세심히 짤 필요가 있겠다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; string s; int f(char x) { return ..
-
[4307] 개미BOJ 2022. 5. 14. 13:54
https://www.acmicpc.net/problem/4307 4307번: 개미 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 www.acmicpc.net 충돌을 고려하지 않으면 각 개미는 왼쪽과 오른쪽, 2가지의 경로만이 존재한다. 가장 빠른 시간은 각 개미의 2가지의 거리중 최소값의 최대값, 가장 느린 시간은 각 개미의 2가지의 거리중 최대값의 최대값 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; ..