목록문제 풀이 (47)
코린이 탈출기
문제 바로가기 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 이해만 잘 하면 금방 풀 수 있다. 톱니바퀴 네 개가 일렬로 놓여져있고, 왼쪽 톱니바퀴의 2번째와 오른쪽 톱니바퀴의 6번째가 맞물려있는데, 회전하는 톱니바퀴 기준으로 맞물린 부분의 극이 서로 다르면 맞물린 다른 톱니바퀴도 도는 방식으로 작동한다. 따라서, 이를 DFS 백트래킹 방식으로 구현하였다. rotate(int num, int dir)가 재귀적으로 호출되며, num은 톱니바퀴 번호, dir은 톱니바퀴가 회전하는 방향 정보를 담고있다. ..
문제 바로가기 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 푸는 데 너무 힘들었던 문제 아기 상어를 BFS로 풀었던 기억이 있어서 아무 생각 없이 BFS로 풀었다가 호되게 당했다 흑흑 BFS로 하다가 DFS로 바꾸면서 로직 다 꼬이고,, 이럴 땐 그냥 덮고 그 다음날 새 마음 새 뜻으로 풀자. 그래서. 이 문제는 BFS로 풀면 안되고 재귀함수를 사용해서 DFS로 풀어야한다. 상어가 갈 수 있는 자리가 여러 곳인데, 상어의 위치를 옮기면 그때마다 물고기의 위치도 다 달라지기 때문에 상어가 움..
문제 바로가기 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 까다로운 문제였다 푸는 데 두시간 걸림 ㅜㅅㅜ 노잼.... #include #include #include #include using namespace std; int R, C, T; int map[50][50]; int new_map[50][50]; int dir[50][50]; int pos[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; //아래, 위, 오, 왼 int dust_cnt; vector clean; //0: ..
문제 바로가기 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 엄청 재밌는 문제였다. 읽고 문제 이해하는 데 한참 걸렸는데 규칙을 찾으니까 신기했다. 세대가 하나 증가할 때마다 그 전 세대의 벡터의 방향들을 하나씩 증가시켜서 거꾸로 저장하면 된다. 벡터의 방향을 모두 저장해두고 벡터의 size 만큼 반복하면서 현재 위치에서 저장된 방향으로 이동시킨다. 정사각형을 만드는 지 확인해야하니까 이동시키면서 각 위치는 map이라는 2차원 배열에 저장해두었다. 그리고 마지막으로, 정사각형을 만..
문제 바로가기 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제 역시 삼성 역량테스트 기출 문제이다. 크게 어렵지는 않았지만 처음 생각해낸 것보다 더 간단하게 풀 수 있었다. 가로줄 N번, 세로줄 N번을 봐줘야 하기 때문에 이를 함수로 구현해도 깔끔하게 안되고.. 어떻게 하면 좋을까 고민하다가 결국 가로줄, 세로줄 함수를 따로 두 개를 만들어서 풀었는데 그렇게 할 필요가 없었다. 세로줄 부분을 복사해서 가로줄 밑에다가 넣어주고 2*N번만큼 가로줄을 확인해주면 되는 것이었다 !!! 세상엔 똑똑한 사람들이 참 많구나.. 그리고 L..
문제 바로가기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 삼성 역량테스트 기출 문제를 풀어보았다 어렵지는 않은데 까다로운 문제.. 국어도 잘해야 빨리 풀 수 있을 것 같다 나는 동이랑 서 방향을 헷갈려서 거기서 오래걸렸다 헷갈리기 시작하면 끝도 없으니까 한 방에 제대로 이해하고 풀어야겠다 #include #include #include #include using namespace std; int N, M; int visited[50][50]; int map[50][50]; pair start; int d..
문제 바로가기 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net BFS로 풀었다. 문제 읽고 정말 빨리 풀 수 있을 줄 알았는데.. 처음 제출하고 시간초과 떠서 2중 for문 하나 지우려고 삽질 오지게 했다 어차피 그거 지워도 시간복잡도 똑같잖아 멍처아 !!!!!!!! memset 바꾸고 vector도 배열로 바꾸고 오만짓 다해봤는데 계속 58%에서 시간초과 ㅠ 알고보니 모든 map의 값이 0인지 확인하는 변수를 전역변수로 선언해서였다 앞으로 이런 실수는 하지말자 #include #include #in..