본문 바로가기
반응형

분류 전체보기1310

[BOJ] 백준 1347 미로 만들기 출처: https://www.acmicpc.net/problem/1347 Input 5 RRFRF Output .. .# 문제에서 N이 0보다 크고 50보다 작다고 했으므로 상하좌우 어떤 방향이든 한 방향으로만 가는 경우를 고려해서 미로의 크기를 101 × 101 설정 따라서 시작점을 배열의 가운데 지점 (50, 50)으로 설정 이 문제에서는 map[101][101] 크기에서 실제 미로의 크기를 추출해야 합니다. 직사각형 미로에서 기준점격인 시작점과 끝점을 알아야 합니다. 시작점과 끝점을 시작 위치(50,50)에서 이동할 때마다 비교해서 x, y의 최솟값(왼쪽 맨 위)이 시작점, x,y의 최댓값(오른쪽 맨 아래)이 끝점이 되도록 갱신해줍니다. 최종적으로는 직사각형 범위만큼을 출력합니다. #include .. 2021. 2. 26.
[BOJ] 백준 1986 체스 출처: https://www.acmicpc.net/problem/1986 Input 4 4 2 1 4 2 4 1 1 2 1 2 3 Output 6 일반 체스와 다른 점은 Pawn은 상대팀의 말을 잡을 수 없기에 공간만 차지하고 있다고 보면 됩니다. Queen → Knight → Pawn 순으로 위치를 입력받습니다. 움직일 수 있는 Queen과 Knight에 대해 잡을 수 있는 공간을 board[][]에 표시합니다. #include using namespace std; char board[1002][1002]; int N, M, cnt, answer = 0; int Q_dx[] = { 0, 0, -1, 1, -1, -1, 1, 1 }; int Q_dy[] = { -1, 1, 0, 0, -1, 1, -1, .. 2021. 2. 26.
[BOJ] 백준 1331 나이트 투어 출처: https://www.acmicpc.net/problem/1331 Input A1 B3 A5 C6 E5 F3 D2 F1 E3 F5 D4 B5 A3 B1 C3 A2 C1 E2 F4 E6 C5 A6 B4 D5 F6 E4 D6 C4 B6 A4 B2 D1 F2 D3 E1 C2 Output Valid 6 x 6 체스판에서 나이트가 이동하므로 나이트 투어를 위해서는 처음 지점을 포함해서 총 36개 칸을 지나쳐야 합니다. 먼저, 주어진 경로대로 나이트가 이동할 수 있는지 확인합니다. 나이트가 한번에 이동할 수 있는 지점은 아래와 같습니다. 주어진 입력은 모든 칸을 순서없이 나열한 것이므로 이동 가능 여부만 확인하며, 별도 모든 칸을 투어했는지는 확인할 필요가 없습니다. 그리고, 마지막 지점에서 다시 처음지점으.. 2021. 2. 26.
[BOJ] 백준 1107 리모컨 출처: https://www.acmicpc.net/problem/1107 Input 5457 3 6 7 8 Output 6 ① 숫자 버튼 없이 +,-로만 조작하는 경우 abs(N - 100); ② 숫자 버튼으로 이동 후 +,-로 조작하는 경우 모든 채널에 대해서 고장 버튼을 고려해서 이동가능한지 확인 후, 해당 채널에서 +,-를 몇 번 눌러야 하는지 확인합니다. Q. N의 최대값은 500,000인데 0 ~ 1000,000채널까지 탐색하는 이유? A. 고장난 버튼에 따라서 50만 위에서 -버튼을 누르는게 좋을 수도 있기 때문에 여유롭게 크기를 잡음 Q. 수학적인 접근 방법이 있을까? N 채널의 차이를 최소로해서 Greedy 방식으로 접근할 수 있지만, Input 1555 8 0 1 3 4 5 6 7 9 O.. 2021. 2. 26.
[BOJ] 백준 3048 개미 출처: https://www.acmicpc.net/problem/3048 Input 3 3 ABC DEF 2 Output CDBEAF 개미 그룹이 서로 →← 방향으로 맞닥뜨렸을 때 swap이 일어나는 것을 구현 ▶ 오른쪽으로 이동중인 개미가 왼쪽으로 이동중인 개미와 마주쳤을 때 서로의 위치를 바꾼다. 개미의 정보를 구조체로 처리 ▶ dir : 개미의 방향, ID: 개미 이름 #include using namespace std; #define RIGHT 0 // 오른쪽으로 이동 #define LEFT 1 // 왼쪽으로 이동 struct ant { int dir; char ID; }; // 개미는 총 알파벳 수만큼 존재 struct ant temp, ants[27]; void swap(int A, int B.. 2021. 2. 26.
[BOJ] 백준 5566 주사위 게임 출처: https://www.acmicpc.net/problem/5566 Input 10 5 0 0 5 6 -3 8 1 8 -4 0 1 3 5 1 5 Output 5 ① 주사위로 이동한 위치 ② 칸에 적힌 지시사항으로 이동한 위치 → 움직인 위치가 도착점(=N)을 지나쳤는지 확인 #include using namespace std; int N, M, board[1001], dice[1001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i = 1; i > board[i]; for(int i = 1; i > dice[i]; int answer = 0, cur = 1; w.. 2021. 2. 26.
[BOJ] 백준 10990 별 찍기 - 15 출처: https://www.acmicpc.net/problem/10990 Input 4 Output * * * * * * * 입력 값 n이 증가함에 따라 별들의 간격과 벌어지는 규칙을 쉽게 확인할 수 있습니다. ▶ 첫번째 줄 n - 1 만큼의 공백과 『*』 ▶ 첫번째 줄을 제외하고는 아래와 같은 규칙을 가집니다. ① n - i 만큼의 공백 문자 출력 후 『*』 ② (i -1) * 2 - 1 만큼의 공백 문자 출력 후 『*』 출력 후 줄넘김 ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 .. 2021. 2. 26.
[BOJ] 백준 13015 별 찍기 - 23 출처: https://www.acmicpc.net/problem/13015 Input 2 Output ** ** *** ** ** 별도 메모리를 잡지 않고 2n - 1 줄에 거쳐 출력. 3가지 영역으로 구분합니다. 첫번째 / 중간 / 마지막 (첫번째와 마지막은 동일한 출력) ① 초기 a, b, c, d의 값은 아래와 같습니다. ▶ a = 0 , b = n - 1 ▶ c = 3n - 3, d = 4n - 4 n번째 줄까지는 a와 b는 증가 / c와 d는 감소 n번째 줄 이후로는 a와 b는 감소 / c와 d는 증가 ② 별을 찍는 형태는 아래와 같습니다. [첫번째와 마지막 줄] ▶ a 별 b 공백 c 별 d [중간] ▶ 공백 a 공백 b 공백 c 공백 d * n번째 줄에 해당하는 정가운데에서는 b와 c가 같은.. 2021. 2. 26.
[SWEA] 3947 가장 짧은 길 전부 청소하기 출처: [SWEA] SW 문제해결 심화 - 증명의 중요성 Input 2 5 5 1 2 1 4 3 2 1 3 1 2 4 2 5 4 3 4 4 1 2 1000 2 3 100 3 4 500 1 4 600 Output #1 7 #2 1700 [1] - [2], [2] - [4], [4] - [5], [1] - [3] 가중치 합: 1 + 2 + 3 + 1 = 7 위의 예제로만 보면 최소 신장 트리를 구성하는 Prim's Algorithm을 적용하면 되지만, [Test Case #2] 가중치 합: 1000 + 600 + 100 = 1700 입니다. [정점 [1] 기준 Prim's Algorithm 결과] 이는 최소신장트리 ≠ 최단 경로이기 때문입니다. 최소신장트리에서는 정점[1] → [2]까지 600 + 500 +.. 2021. 2. 25.
[BOJ] 백준 1916 최소비용 구하기 출처: https://www.acmicpc.net/problem/1916 Input 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 Output 4 출발점 X부터 다른 정점 Y까지의 최소거리 비용을 구하기 위해 다익스트라(Dijkstra)을 이용 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com 정점과 간선의 개수가 비교적 크지 않으므로 선형적으로 구현 * 문제에서 Input Data 중 아래와 같이 서로 다른 .. 2021. 2. 25.
반응형

티스토리툴바