반응형 알고리즘/[ADV] 삼성 SW 역량 테스트 A형 상시9 BOJ 17472 : 다리 만들기 2 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17472 아래의 순서대로 구현한다. 1) BFS를 이용해 섬을 구분한다. 2) 섬과 섬 사이의 거리를 구한다. 3) 섬의 개수 N에 대해, 다리 N - 1개를 선택하여 모두 연결되어 있다면, 다리의 길이를 갱신한다. 구조체는 좌표를 기억하기 위한 RC 구조체가 필요하다. MAP 주변은 모두 -1로 처리하고 (1, 1)부터 입력을 받는다. connect 배열은 섬과 섬 사이의 거리를 저장하기 위한 배열이다. 섬과 섬 사이의 거리는 가장 가까운 거리만 필요하므로, 큰 값(WORST = 0x7fff0000)으로 초기화한다. islandList는 각 섬의 좌표를 .. 2021. 5. 1. BOJ 17471 : 게리맨더링 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17471 A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다. (N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.) 만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다. people 배열에는 구역의 인구 수를 저장한다. #define MAX (10 + 5) int N; int MAP[MAX][MAX]; int people[MAX]; void input() { scanf("%d", &N); for (int i = 1; i 2021. 4. 28. BOJ 17406 : 배열 돌리기 4 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17406 MAP은 (1, 1)부터 input을 받고, COMMAND 구조체에 (r, s, c)를 저장한다. #define MAX (50 + 10) int N, M, K; int MAP[MAX][MAX]; typedef struct st { int r; int c; int s; }COMMAND; COMMAND command[10]; void input() { scanf("%d %d %d", &N, &M, &K); for (int r = 1; r 2021. 4. 24. BOJ 3954 : Brainf**k 인터프리터 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/3954 명령어를 쉽게 판단하기 위해 아래와 같이 define하자. typedef unsigned char uc; #define MAX (50000000) #define DECREASE ('-') #define INCREASE ('+') #define POINTER_LEFT ('') #define POINTER_RIGHTJUMP ('[') #define POINTER_LEFTJUMP (']') #define OUTPUT ('.') #define READ_AND_SAVE (',') #define MODULO (256) 괄호의 짝을 찾는 방법은 BOJ 9012 .. 2021. 4. 21. BOJ 17281 : ⚾ (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17281 9명의 타자가 있고 1번 타자는 4번에 고정이므로, 8! = 40320번의 경우의 수에 대해 시뮬레이션을 하면 된다. 9명 타자를 줄 세우는 방법은 N과 M (1) - 순열의 방법을 이용한다. input에서는 간단히 player의 결과를 저장한다. void input() { scanf("%d", &N); for (int i = 1; i 2021. 4. 17. BOJ 17136 : 색종이 붙이기 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17136 input에서 색종이 상태를 입력받고, 색종이의 개수 PAPER_COUNT에 저장해둔다. 그리고 각 색종이의 최대 개수인 5를 MAX_PAPER[1~5]에 저장한다. #define MAX (10 + 10) int MAP[MAX][MAX]; int PAPER_COUNT; int MAX_PAPER[10]; void input() { for (int r = 0; r < 10; r++) { for (int c = 0; c < 10; c++) { scanf("%d", &MAP[r][c]); PAPER_COUNT += MAP[r][c]; } } for (in.. 2021. 4. 14. BOJ 17135 : 캐슬 디펜스 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17135 먼저 궁수가 탐색해야할 우선순위를 구해보자. 아래의 그림은 D = 1, 2, 3인 경우 궁수가 탐색해야하는 순서다. 적이 가장 가까울 경우 가장 왼쪽에 있는 적을 공격한다고 하였으므로, 거리가 가장 가까운 앞을 보고, 그 다음 거리부터는 왼쪽/가운데/오른쪽 순서대로 탐색한다. D = 4인 경우, 규칙이 점점 보인다. 위의 탐색 순서를 궁수를 기준으로 r, c로 나타내면 아래와 같다. 좌표 r은 -1부터 시작해서 감소하다가 다시 증가한다. 좌표 c는 처음엔 0이며, 그 다음 주기에는 -1 부터 1씩 증가, 그 다음은 -2부터 1씩 증가한다. 이 주기.. 2021. 4. 11. BOJ 17070 : 파이프 옮기기 1 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17070 파이프는 오른쪽, 아래, 대각선으로만 진행하므로 방향을 3개 define한다. input에서는 MAP 주변에 벽을 세운다. #define MAX (16 + 5) #define RIGHT (0) #define DOWN (1) #define RIGHT_DOWN (2) int N; int MAP[MAX][MAX]; void input() { scanf("%d", &N); for (int r = 0; r 2021. 4. 8. BOJ 16637 : 괄호 추가하기 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/16637 첫 번째 예시를 보자. 연산자는 + * - * 로 총 4개이다. 순서대로 1, 2, 3, 4번째 연산자로 정의하자. 먼저 괄호 안에는 연산자가 하나만 들어있어야 하므로, 1번 연산자에 괄호를 만들면, 2번 연산자는 괄호가 불가능하다. → (3 + 8) * 7 - 9 * 2 따라서 DFS로 아래의 경우의 수가 되도록 만든다. 0 0 0 0 → 괄호가 없는 경우 0 0 0 1 → 4번 연산자에만 괄호를 만든 경우 0 0 1 0 0 1 0 0 0 1 0 1 → 2번, 4번 연산자에 괄호를 만든 경우 1 0 0 0 1 0 0 1 1 0 1 0 1 2 3 .. 2021. 4. 5. 이전 1 다음 반응형
