어흥

문제 링크: https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 1. 주의할 점 - 알파벳이 최대 10개 -> A~Z 사이 임의의 10개가 최대다 2. 구현 - 첫 번째 방법: 브루트포스(DFS)를 이용하여 구현한다 - 알파벳을 모든 경우로 배치하는 방법 : 10! -> 약 360만이므로 2초내에 충분히 계산 가능하다 - 두 번째 방법: 그리디 알고리즘으로 ..

문제 링크: https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. 주의할 점 - BFS를 잘못 사용할 경우 시간초과가 발생한다 - K의 값이 0~10이므로 Check[1000][1000][11]로 설정해야 한다 -> 11 대신 10을 사용할 경우 틀린다 - 낮의 경우에만 벽을 부술 수 있다 2. 구현 - 벽 부수고 이동하기 1이나 2와 비슷한 방법을 사용하지만, 낮과 밤의 구분을 추가한다 - 낮일 경우(Sun..

문제 링크: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. 주의할 점 - K의 값이 0~10이므로 방문 배열 Check[1000][1000][11]로 설정한다 - 출발지점도 포함이다 2. 구현 - 구조체를 이용하여 X좌표, Y좌표, 벽을 부순 횟수를 저장하는 Queue를 통해 BFS 탐색을 한다 - 4방향을 탐색하며, 벽이 아닌 경우 현재 벽을 부순 횟수로 이동하려는 지점을 방문한 적이 없다면 Queu..

문제 링크: https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 문제 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다. 상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최 www.acmicpc.net 1. 주의할 점 - 첫 나무를 다 심으면 2일이다 - 정렬을 해야 한다 2. 구현 - 입력받은 Arr배열을 정렬한다 - ..

문제 링크: https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - "RGB거리"문제와 시작점과 끝점이 접해져 있다는 가정만 제외하면 똑같다 - 시작점과 끝점이 같다면 최소값으로 치면 안된다 2. 구현 - Cost[]: 집에 색을 칠했을 때 지불해야 하는 비용 - DP[N][3]: N번째 집에 R,G,B를 칠했을 때 지불해야 하는 총 비용 - 첫 번째 집에 M번을 칠했다는 가정하에 구하..

문제 링크: https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 www.acmicpc.net 1. 주의할 점 - 타일 1개에는 2개의 원소가 포함된다 - N의 범위가 500이하이므로 최대범위는 501까지로 설정한다 ->..

문제 링크: https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - Node의 최대가 10만개다 -> Vector를 사용한다 - Root Node는 1이다 2. 구현 - BFS를 통해 구한다 - Queue에 1을 넣고 시작한다 - Queue에서 Pop한 원소에 맞닿아있는 다른 Node들이 방문하지 않은 상태라면 해당 Node들의 부모를 현재 Pop한 Node로 설정한 후, 큐에 추가한다 - 위의 과정을 모든 Node에 방문할 때 까지 진행한다. #include #include #include u..

문제 링크: https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 1. 주의할 점 - DFS를 통해 10번이상 실행하지 않도록 설계한다. - 구슬이 겹쳐지는 경우 따로 처리한다 2...