목록문제 풀이 (47)
코린이 탈출기
문제 바로가기 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 조합 + BFS로 풀 수 있다 놓을 수 있는 치킨 집을 조합으로 계산하고 치킨집 각 집의 거리를 구하기 위해 BFS를 하면 된다. 조합으로 풀 수 있는 문제가 참 많구만 ~ #include #include #include #include #include using namespace std; //조합, bfs 함께 풀면 됨 int N, M; int map[50][50]; int dist[50][50]; int pos[4][2] =..
문제 바로가기 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제이다 sort함수에서 compare 함수로 custom하게 사용할 수 있다는 것을 알게됐다 R_calculate이랑 C_calculate이랑 로직은 똑같은데 수행하는 게 열 기준/행 기준만 다른데,, 두개를 합치면 더 간단한 코드가 될 수 있을 것 같은데 모르겠당 ㅎ #include #include #include #include using namespace std; int arr[201][201]; int ncount[2..
문제 바로가기 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 위의 그림과 같은 사다리가 주어졌을 때, i번째 선이 i번째로 나오게 하는 최소한의 사다리 개수를 출력하는 문제이다. 사다리를 0개부터 3개까지 놓을 수 있기 때문에 사다리를 늘려가면서 놓을 수 있는 모든 경우의 수를 계산해야한다. 사다리를 놓는 부분은 백트래킹으로 구현하였다. solve() 함수 내에서 for (int i = 1; i a >> b; ladder[a][b] = 1; } N--; for (int i = 0; i
문제 바로가기 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 청소년 상어 문제 풀면서 제대로 안 읽었다가 호되게 당한 기억이 있어서.. 이번 문제는 풀기 전에 충분히 생각하고 풀었다. 문제를 풀다보니 대충 생각하고 무작정 코드부터 짜면 로직이 꼬이거나 실수가 많아져서 결국은 시간이 더 오래걸린다는 것을 체득했다. 그래서 ! 이젠 확실히 문제를 이해할 때까지 아이패드에 적어보고 문제에서 요구하는 사항을 완벽히 이해하고 푸는 연습중이다. 이렇게 하니 코드 짜면서 헷갈릴 일이 적어서 오히려 더 빨리 ..
문제 바로가기 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 테트로미노를 이루는 도형들의 좌표를 tetromino 배열에 넣어서 완전탐색으로 구현하였다. 처음에는 5개의 테트로미노만 배열에 넣고 회전이나 대칭시키는 것을 for문 내에서 하려고 했는데, 코드가 너무 어려워질 것 같아서 회전, 대칭 시켰을 때 모양이 겹치지 않는 19개의 테트로미노를 직접 구했다. 이 19개의 좌표를 모두 넣는 것이 상당한 노가다,, 좌표 넣으면서 실수해서 푸는 데 시간이 좀 걸렸다. 코드 내에 for문이 무려 4중 포문이였지만..
문제 바로가기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 이해만 제대로 하면 쉽게 구현이 가능한 문제이다. 특별한 알고리즘이 필요없다! 주사위를 동, 서, 남, 북으로 굴릴 때 주사위의 번호 위치가 어떻게 바뀌는지만 생각해주면 된다. change_dice 함수에서 주사위의 번호를 바꾸는 구현을 했다. #include #include #include using namespace std; int N, M, K; int arr[20][20]..
문제 바로가기 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백트래킹으로 스타트 팀과 링크 팀의 팀원을 구하고, 2중 for문으로 각 팀의 점수를 계산하여 차가 가장 작은 것을 구하면 된다. 처음 풀었을 때 시간초과가 떠서 띠용.. 생각해보니 팀을 나누는 부분에서 중복계산이 있었다는 것을 찾았다. - 시간초과가 난 dfs 코드 void dfs(int digit) { if (digit == n / 2) { minn = min(minn, compare()); return; } for (int i = 0; i < n; i++) { if..
문제 바로가기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 딱 문제를 읽어보면 백트래킹 냄새가 솔솔 ~ 역시나 백트래킹으로 구현하니 아주 쉽게 풀 수 있었다 백트래킹으로 문제를 풀 때는, 기존의 상태에서 어떠한 연산이나 수행으로 바뀐 상태를 다시 원래대로 돌려놓는 것이 중요하다. dfs()함수에서 다른 상태로 갈 때 바뀌는 값이 res와 2차원 배열 visited 이므로, 재귀함수를 호출한뒤 다시 원래의 res와 visited로 돌려주어야한다. 또..