문제 가르침 문제 바로가기 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 풀이 brute force로 찾기 (N이 작음) 조건들을 이용하여 최대한 시간복잡도 줄이기 ..

난이도 : ? 걸린 시간 : 1시간 반 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다. 이제 원숭이..

난이도 : 골드 2 걸린 시간 : 1시간 문제 퍼즐 문제 바로가기 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 풀이 최단 경로 문제이므로 bfs 이용 memo 해야 똑같은 경로 다시 탐색 x memo는 전체 map의 상태를 저장해야함 string으로 저장 코드 #include #include #include #include #include using namespace std; int map[..

난이도 : 골드 5 걸린 시간 : 1시간 30분 문제 DSLR 문제 바로가기 풀이 DSLR이라는 4가지 경로가 있다고 생각하고 bfs 코드 #include #include #include using namespace std; struct point { int prev; char state; int visited = -1; }; char dslrArr[4] = { 'D', 'S', 'L', 'R' }; int dslrResult(int type, int num) { int tmp; switch (type) { case 0 : return (num* 2) % 10000; case 1 : if (num == 0) return 9999; else return num - 1; case 2 : tmp = num /..

난이도 : 골드 3 걸린 시간 : 30분 문제 다리 만들기 문제 바로가기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리 모든 섬 사이의 최단 거리를 구해야 함 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산 가중치 없으므로 bfs 이용 각 섬에 속하는 점들은 bfs로 따로 찾기 코드 #include #include using namespace std; int map[101][101]; int direction[4][2] = { ..

난이도 : 골드 5 걸린 시간 : 30분 문제 보물섬 문제 바로가기 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다. 예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다. 보물..

난이도 : 골드 4 걸린 시간 : 오래 걸림 문제 벽 부수고 이동하기 문제 보러가기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 풀이 모든 경로를 살펴볼 필요없..

난이도 : 골드 4 걸린 시간 : ㅎㅎ.. 오래 걸림 문제 아기 상어 문제 바로가기 풀이 bfs를 이용하여 먹을 수 있는 고기 찾기 + 상어로부터의 거리 찾기 거리가 가장 가까운 먹을 수 있는 고기들 찾기 그 중 가장 왼쪽 위에 있는 고기 찾기 상어가 해당 물고기의 위치로 이동해서 먹고, 먹은 물고기 개수가 size와 같아지면 size 키우기 상어보다 작은 물고기가 없을 때까지 반복 코드 #include #include #include using namespace std; struct shark { int r; int c; int size = 2; }; struct fish { int r; int c; int distance = 0; fish(int rp, int cp, int dist) { r = rp..