목록전체 글 (62)
코린이 탈출기
문제 바로가기 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로 돌려주어야한다. 또..
문제 바로가기 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 이해만 잘 하면 금방 풀 수 있다. 톱니바퀴 네 개가 일렬로 놓여져있고, 왼쪽 톱니바퀴의 2번째와 오른쪽 톱니바퀴의 6번째가 맞물려있는데, 회전하는 톱니바퀴 기준으로 맞물린 부분의 극이 서로 다르면 맞물린 다른 톱니바퀴도 도는 방식으로 작동한다. 따라서, 이를 DFS 백트래킹 방식으로 구현하였다. rotate(int num, int dir)가 재귀적으로 호출되며, num은 톱니바퀴 번호, dir은 톱니바퀴가 회전하는 방향 정보를 담고있다. ..