BOJ
-
[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; ..
-
[17413] 단어 뒤집기 2BOJ 2022. 5. 14. 13:47
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 아마 스택을 사용하면 조금 더 깔끔하게 짤 수 있을 것 같다. ''이 나올때까지 그대로 출력하고 continue ' '이 나오면, 단어를 출력한다. 루프가 끝난 다음에도 아직 출력하지 않은 단어가 존재할 수 있으므로 한번 더 체크해준다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local =..
-
[17485] 진우의 달 여행 (Large)BOJ 2022. 5. 14. 13:40
https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dp[n][m][3] 형태로 테이블을 만들어서, 현재 방향과 다른 방향인 곳 2개중 작은것을 취한다. 편의상 1-base index를 사용하고, [1..n][1..m]이 아닌 다른곳은 INF로 채워주어서 방향을 신경쓰지 않고 min()으로 선택하는 도중에 자연스럽게 배제되도록 하였는데, 계산 과정중 a[i][j] + INF가 INT_MAX를 넘으면 문제가 될..