BOJ
-
백준 (BOJ) 16958번 텔레포트알고리즘 풀이/백준(Boj) 2020. 6. 2. 19:01
문제 : https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 풀이 : 우선 2차원 행렬인 dist를 통해 A와 B의 거리를 계산해 놓는다. 그리고 직접 가는 방법 A -> B에 값을 구한다. 이때 A와 B가 둘 다 특별한 도시라면 T로 갱신할 수 있는지 체크해주어야 한다. 이제 더 작아질 수 경우는 A,B에 가장 가까운 곳을 방문해서 T를 이용해 가는 방법이다. 해당 경우가 더 작아지면 갱신해주게 된다...
-
백준(BOJ) 16943번 숫자 재배치알고리즘 풀이/백준(Boj) 2020. 5. 4. 14:43
문제 : https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net 풀이 : A의 크기는 10^9 미만 이므로 최대 8자리 밖에 가지지 않는다. 따라서 모든 경우를 하나하나 해봐도 시간 안에 가능하고 이는 next_permutation으로 처리하였다. ans는 b보다 작은 값이면 갱신하게 된다. 코드 ( C++ )
-
백준(BOJ) 2174번 로봇 시뮬레이션알고리즘 풀이/백준(Boj) 2020. 4. 20. 12:55
문제 : https://www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 문제 가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다. 이 땅 위에 로봇들이 N(1≤N≤100)개 있다. 로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. 위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다. 또한 각 로봇은 맨 처음에 NWES 중 하나의 방향을 향해 서 있다. 초기에 서 있는 로봇들의 위치는 서로 다르다. 이러한 로봇들에 M(1≤M≤100)개의 명령을 내리려고 한다. 각각의 명령은 순차적으로 www.acmicpc.net 풀이 : v라는 배열에는 각 로봇들의 index와 상태들을 저장해 놓는 곳이다. 따라서 한 로봇이 할 일을 끝냈다면 갱신해..
-
백준(BOJ) 17085번 십자가 2개 놓기 (수정)알고리즘 풀이/백준(Boj) 2020. 4. 18. 00:05
문제 : https://www.acmicpc.net/problem/17085 17085번: 십자가 2개 놓기 첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 : 기존에는 a를 모두 늘리고 b를 구했지만 재채점 이후로는 틀리다고 나오므로 a를 늘리는 도중에 b를 늘리면서 ans를 구하는 방식으로 접근했습니다. 전체 n*m이 작기에 충분히 시간 안에 가능합니다. 코드 ( C++ )
-
백준(BOJ) 1806번 부분합알고리즘 풀이/백준(Boj) 2020. 4. 15. 03:07
문제 : https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 풀이 : 완전 탐색을 이용 시 n이 크기에 시간 내에 처리하지 못하고 투 포인터를 이용해서 처리해보자 lo와 hi는 인덱스를 가리..
-
백준(BOJ) 1022번 소용돌이 예쁘게 출력하기알고리즘 풀이/백준(Boj) 2020. 4. 14. 12:40
문제 : https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다. www.acmicpc.net 풀이 : 1.r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같으니 board배열은 [50][5]로 처리하자. 2.while문은 네 꼭짓점이 모두 0이 아닐 때까지 계속된다. 3. y 에다 r1를 빼고 x에다 c1을 뺀 것을 처음 값으로 두자. 예제와 같이 (0-(-3), 0-(-3))으로 (3,..
-
백준(BOJ) 16638번 괄호 추가하기 2알고리즘 풀이/백준(Boj) 2020. 4. 9. 15:26
문제 : https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, www.acmicpc.net 풀이 : 기존 괄호 추가하기 문제는 단순히 해당하는 괄호 연산 (A 연산자 B) 를 ( A 연산자 B + 0 ) 의..