알고리즘 풀이/백준(Boj)
-
백준(BOJ) 16925번 문자열 추측알고리즘 풀이/백준(Boj) 2020. 6. 12. 14:21
문제 : https://www.acmicpc.net/problem/16925 16925번: 문자열 추측 첫째 줄에 문자열 S의 길이 N(2 ≤ N ≤ 100)이 주어진다. 다음 2N-2개의 줄에 걸쳐서 문자열 S의 접두사와 접미사가 한 줄에 하나씩 주어진다. 모든 접두사와 접미사가 주어지기 때문에, 길이가 i(1 � www.acmicpc.net 풀이 : 좀 더 나은 간단한 풀이가 있겠지만 일단 처음 떠올랐던 그대로 풀이를 작성하겠다. 예제 1번 ) 5 ba a abab a aba baba ab aba 으로 설명해보자면 우선 크기로 정렬 시 a a ab ba aba aba abab baba 가 나오게 된다. (1)(2) (3) (4) 이때 정답이 되는 문자는 (1) + (3) , (1) + (4) , (2..
-
백준(BOJ) 16951 블록 놀이알고리즘 풀이/백준(Boj) 2020. 6. 9. 14:36
문제 : https://www.acmicpc.net/problem/16951 16951번: 블록 놀이 욱제는 높이가 1인 블록을 매우 많이 가지고 있고, 블록을 쌓아서 탑 N개를 만들었다. 탑은 일렬로 배열했고, 왼쪽에서부터 i번째 탑의 높이는 Ai이다. 욱제가 가장 좋아하는 정수는 K이다. 따라서 www.acmicpc.net 풀이 : 해당 배열 인덱스 하나당 기준으로 잡고 k 만큼 차이나는 배열을 만들어보자. 예를 들어 2 4 6 9이고 k가 1이라면 2 3 4 5 3 4 5 6 4 5 6 7 6 7 8 9 이 4개의 후보들 중 정답이 있게 된다. 이때 새로 만든 배열이 1보다 작다면 바로 pass 하자. 코드 (C ++ )
-
백준 (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) 15831번 준표의 조약돌알고리즘 풀이/백준(Boj) 2020. 4. 15. 03:26
문제 : https://www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다. www.acmicpc.net 풀이 : 완전 탐색은 시간 초과가 나므로 투 포인터를 이용해서 처리하자. lo와 hi 인덱스를 0으로 둔 후 조건을 만족하면 범위의 최댓값을 구하는 연산을 해준다. 코드 ( C++ )