[PS][기출문제] 삼성

삼성 기출문제입니다.

---

주사위 윷놀이

문제의 정답은 여기에서 확인할 수 있습니다.

1. map에서 같은 점수를 가진 여러 개의 node가 존재합니다. 따라서 점수별로 구분하는 것이 아니라, 노드에 임의의 idx를 부여해서 구별합니다.
2. horse class를 만들고 겹치는지를 판단합니다.
3. 시작 위치와 마지막 위치에서의 코너 케이스에 주의합니다.
4. 모든 경우의 수에 대해서 백트래킹을 진행하면서 각각의 경우에 대해서 말을 옮기는 것을 진행합니다.
   1. 이 때 경우의 수는 i번째의 주사위 결과를 0~4번째의 말 중 어떤 말을 옮길지 모두 따저야합니다.
   2. 만약 입력이 5 5 5 5 5 1 1 1 1 1일 때, 움직일 말의 idx가 0 0 1 1 1 0 0 1 1 1이라면 3번째 4번째 주사위 결과를 1번말이 수행하지 못합니다. 이 때 1번말을 움직이지 않고 다음 번쨰의 주사위를 던지는 것이 아니라, 특정 번째의 주사위를 던지지못하면 그 때의 case는 아예 제외해야합니다. 정상적인 경우라면 3번째 주사위 결과를 1번말이 움직이지 못하면 다른 말로 움직일 것이기 때문에 바로 다음 경우의 수로 넘어가야합니다.
5. 3시간 이상 걸렸습니다.(20.4.23)

이차원 배열과 연산

문제의 정답은 여기에서 확인할 수 있습니다.

1. 문제 조건에 따라서 진행하면 시간초과 없이 풀 수 있는 시물레이션 문제입니다.

나무 재테크

문제의 정답은 여기에서 확인할 수 있습니다.

1. 나무가 겹치는지 판단해야하는 부분에서 시뮬레이션의 이동시키기/순환시키기의 방법으로 접근했다가 낭패를 본 문제입니다.
2. 나무는 생성된 자리에서 나이가 자라거나 사라기지만 합니다. 따라서 나무가 애초에 저장되는 좌표는 고정이고 나이만 vector에 push하면 됩니다.
3. map[][]에 int만 넣으면 되는데 불필요한 TREE 자료형을 만들어서 push를 진행하면 시간초과가 나오는 문제입니다.
4. 나무가 사라질 때, 어느 좌표에서 나이가 몇인 나무가 죽었는지만 저장해두고 사용하면 됩니다.

아기 상어

문제의 정답은 여기에서 확인할 수 있습니다.

1. 문제 조건에 따라서 진행하면 시간초과 없이 풀 수 있는 시물레이션 문제입니다.
2. 먹이까지의 거리가 필요하기 때문에 dfs가 아닌 bfs로 접근합니다.

스타트와 링크

문제의 정답은 여기에서 확인할 수 있습니다.

1. next_permutation 풀이
2. n/2개만큼 1을 집어넣은 arr에 대해서 next_permutation을 수행한다.
3. 0이 들어있는 선수는 a팀, 1이 들어있는 팀은 b팀
4. [0,n]에 대해서 오름차순으로 두 명의 선수를 선택한다. 이 두 선수가 같은 팀인 경우 해당되는 팀에 점수를 더한다.
5. n = 6, arr[6] ={0,0,0,1,1,1}를 예로 들면 6개 중에서 2개를 선택하고 이 두개가 같은 경우만 점수를 계산한다.
6. recur() 풀이 : 위 링크의 댓글에 코드 있습니다.
7. depth 번째 선수에 대해서 어떤 팀에 소속될지 선택해줍니다.
8. 단, 각 팀의 수는 최대 n/2명을 넘지 않도록 합니다.
9. 이렇게하면 depth == n이 되었을 때 양 팀 모두 n/2명씩 선택되게 됩니다.
10. 주의할 점은 각 팀을 선택하고, recur()가 끝났을 때 그 팀을 선택한 것을 취소해주어야 합니다.
11. 선택이 완료되면 양 팀은 n/2명씩 선수를 가지고 있고, 두 선수를 선택할 때 index가 증가하도록 선택해주면 됩니다.

인구 이동

문제의 정답은 여기에서 확인할 수 있습니다.

1. n이 작고 시간이 넉넉해서 맵을 여러번 순회해도 되는 문제입니다.

경사로

문제의 정답은 여기에서 확인할 수 있습니다.

1. 모든 길을 양방향에서 확인한 코드는 위 링크의 댓글에 있습니다.
2. 간단한 아이디어로 짧고 간결하게 풀이한 방법은 링크의 본문입니다.
3. 먼저 좌우 방향과 위아래 방향의 알고리즘은 똑같을 것입니다. 따라서 map[200][100] 배열을 만들고 동일한 알고리즘은 같은 for문에서 돌릴 수 있도록 합니다.
4. cnt는 현재까지 높이가 같은 칸의 수 입니다.
5. 모든 row에 대해서 오른쪽으로 이동하면서, 오른쪽 칸이 한 칸 더 높을 때는 cnt와 l의 크기를 비교해서 놓을 수 있는지 판단합니다.
6. 만약 현재칸이 오른쪽칸보다 높다면, cnt = l-1을 통해서 경사로를 놓기 위해서 몇 칸이 부족한지 나타냅니다.
7. 중간에 2칸 이상 차이나서 break한 경우가 아니고, cnt가 0이상이라면 경사로를 놓을 수 있는 길입니다.

[로봇 청소기]](https://www.acmicpc.net/problem/14503)

문제의 정답은 여기에서 확인할 수 있습니다.

1. 후진할 때 청소하지 않는 것이지 방문한 곳을 다시 방문하지 않는 것이 아닙니다.
2. 모든 좌표를 벽, 청소하지 않은 곳, 청소한 곳으로 나누어서 생각합니다.