Study hard

www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net [풀이] 2020상반기 인턴 sw역량평가에 나왔던 문제. 당시에는 자료구조를 잘못 써서 계속 틀렸다. 문제에 주어진대로 시뮬레이션 하면 된다. 다음의 순서로 구현하였다. 1. 모든 상어가 자신의 위치에 냄새를 뿌린다. 2. 1초마다 모든 상어가 조건대로 이동(방향 우선순위 따라 먼저 빈 칸 찾고, 없으면 우선순위 따라 자신의 냄새가 있는 곳 찾기) 3. 겹치는 상어들..

www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net [풀이] dfs 순열 구하는 방법을 이용하여 회전 연산 순서를 정했다. ※r, c가 1부터 시작한다는 것 유의 회전 연산은 값 하나를 tmp에 저장해놓고 for문을 돌리는 방식으로 구현했다. #include #include //min #include using namespace std; struct Roll { int r, c, s; }; int N, M, K; int A[51][..

www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종� www.acmicpc.net [풀이] dfs 순열 구하는 방법을 이용하여 타순을 구하고 게임 룰대로 시뮬레이션 하면 되는 문제였다. 1. 타순 구하기: 순열 2. 각 타순에 대하여 나올 점수 구하기 3. 최댓값 갱신 ※다음 이닝으로 넘어갈 조건, 타순 만드는 조건 등 주위깊게 보기! #include #include using namespace std; int N; int Results[50][10]; int Order[10]; bool che..

www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net [풀이] dfs를 이용하여 백트래킹을 하였다. 1. 종이에서 1 찾기: 1 없으면 지금까지 붙여왔던 종이 개수와 최솟값 비교하여 갱신 2. 1이 있는 칸에 1*1, 2*2, 3*3, 4*4, 5*5 종이를 붙일 수 있는지 확인(종이 붙이는 범위 안에 0이 있으면 안 됨) 3. 종이를 붙이고 붙인 종이 개수에 +1하여 재귀 4. 붙인 종이 떼기 #include #include using namespa..

www.acmicpc.net/problem/17135 [풀이] 문제에 나온 게임 순서대로 구현하였다. 1. 궁수 3명 배치: dfs를 이용하여 궁수 위치의 조합을 만들어 각 조합마다 게임을 진행하였다. 2. 적의 존재 여부 확인 및 적의 위치 저장(적이 존재하지 않으면 게임 끝) 3. 궁수마다 가장 가까운 적 찾아서 공격: 궁수와 가장 가까운 적을 찾고 그 적이 아직 공격받지 않았다면 공격할 수 있는 적의 수로 카운트 해주고 제외한다. 4. 적 아래로 한 칸 이동: 맵의 범위 넘어가면 제외 ※첫번째 줄부터 아래로 내려가면서 이동시키면 맵이 의도한 것과 다른 모양이 될 수 있으므로 마지막 줄부터 위로 올라가면서 이동시켜야 함!! #include #include #include //memset #includ..

www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] dfs를 이용해서 풀 수 있는 문제였다. 오른쪽, 아래, 오른쪽 아래 대각선 방향으로만 움직이므로 파이프의 오른쪽 부분(이동방향쪽 한 칸)만 고려하면 된다. 일반적인 경로탐색에서 방향을 세 가지로 바꾸고 조건을 추가해주었다. 1. (N-1,N-1)에 도달하면 cnt++ 2. 가로, 세로 방향일 때 그 다음에 이동 가능한 방향인지 확인 3. 대각선 방향일 때 오른쪽, 아래, 오른..