알고리즘/알고리즘 문제 풀이

(C++) 백준 1149번 - RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 house[x][0]은 x번째 집이 빨간색일 때의 최소 비용, house[x][1]은 x번째 집이 초록색일 때의 최소 비용, house[x][2]은 x번째 집이 파란색일 때의 최소 비용을 저장하도록 하였다. #include #include using namespace std; int hous..

(C++) 백준 2579번 - 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다. 마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 ..

(C++) 백준 9095번 - 1, 2, 3 더하기

문제 링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 입력이 1일 때 1, 입력 2일 때 2, 입력이 3일 때 4이라는 초기값을 부여해 준 후, 입력값이 i일 때의 값은 arr[i-1]+arr[i-2]+arr[i-3] 임을 이용해 풀이하였다. #include using namespace std; int arr[12]; int T, n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; arr[1] = 1; ..

(C++) 백준 1463번 - 1로 만들기

문제 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다. #include #include #include using namespace std; int arr[1000002]; int X; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> X; arr[2] = 1; for(int i = 3; i

(C++) 백준 15686번 - 치킨 배달

문제 링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 Permutation을 사용하여 M개의 치킨집들의 조합을 뽑아내고 이에 대한 모든 집에서의 치킨 거리를 구한 후 모두 더함으로써 도시의 치킨 거리를 구하였다. 골드 문제치고 난이도가 어렵진 않다. 다만 Permutation을 사용하여 조합을 뽑아내는 방법에 익숙해질 필요가 있다고 느낀 문제였다. #include #include #include #define..

(C++) 백준 18808번 - 스티커 붙이기

문제 링크 : https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 모든 경우를 고려하여 풀이를 진행해야 하는 브루트포스 문제이다. 스티커를 회전하는 것을 구현하는 방법을 생각하는 것과 스티커를 붙일 수 있는 경우를 판별하는 방법을 구현하는 것이 매우 어려웠다. 또한 checknput() 메서드의 이중 for문 뒤에 위치한 제일 마지막 경우를 체크하기 위한 코드를 생각하지 못해 상당히 헤매었다. #include using namespace std..

(C++) 백준 15683번 - 감시

문제 링크 : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 백트래킹을 사용하여 풀이하였다. 먼저 전체 사무실에서 CCTV가 위치한 곳의 좌표를 Queue에 넣는다. 다음으로 Queue의 Front에 위치한 CCTV가 스캔할 수 있는 지역을 체크한다. 체크한 뒤 사무실의 정보와 Queue를 함수의 변수로 넘겨가면서 Queue가 빌 때까지 재귀적으로 진행한다. #include #include #include #define X f..

(C++) 백준 2910번 - 빈도 정렬

문제 링크 : https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 풀이 stable_sort와 커스텀 비교 함수를 사용하여 풀이하였다. pair를 사용해 값과 빈도수를 동시에 저장하는 것과 stable_sort를 사용하는 것이 중요하다고 할 수 있다. #include #include #include #define X first #define Y second using namespace std; int n, c; vector v; // 첫번째 int는 값, 두번째 int는 나타난 빈도수..

(C++) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 풀이 sort 함수와 커스텀 비교 함수를 사용하여 단어를 정렬하여 풀이를 진행하였다. 다만 C++ vector에서의 중복 제거를 처음 사용해 보아서 조금 어려움도 있었다. ※ unique 함수는 중복된 값들을 뒤로 보내고, 중복된 값들의 시작 위치를 반환한다. ※ erase 함수는 시작 위치부터 종료 위치까지의 값을 모두 제거한다. #include #include #..

(C++) 백준 15657번 - N과 M (8)

문제 링크 : https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 입력받은 수들을 정렬한 후 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int i..