[백준 / C++] 18290번: NM과 K (1)

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 브루트포스 알고리즘, 백트래킹 구현 방법 이전에 풀었던 백준 14502번 연구소 문제 (https://jangkunstory.tistory.com/135)에서 구현했던 걸 구현하는 문제다. N*M개에서 K개 고르기. 연구소 문제에서는 next_permutation 함수를 이용해 nC3을 구현했지만 이번에는 다른 방식으로 풀었다. (그래도..

• format_list_bulleted PS/백준
• · 2023. 9. 25.
• textsms

[백준 / C++] 15686번: 치킨 배달 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 브루트포스 알고리즘, 백트래킹 접근 방법 입력으로 받은 치킨집에서 M개를 고르는 모든 경우의 수를 다 따져보며 치킨 거리를 구한다. 구현 c++의 STL에 있는 next_permutation을 이용해 치킨집 중 M개를 고르는 조합을 만든다. 입력으로 들어오는 치킨집의 개수가 x개라고 하면, x개의 원소 중 M개가 1, ..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms

[백준 / C언어] 14888번: 연산자 끼워넣기 (삼성 SW 기출)

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 브루트포스 알고리즘, 백트래킹 접근 방법 N개의 수 사이 N - 1개의 자리에 모두 들어갈 수 있는 N - 1개의 연산자가 주어지고, 연산은 연산자 우선순위를 무시하고 앞에서부터 진행되므로, 직접 다 하나씩 집어넣어보는 브루트포스 알고리즘을 사용한다. 구현 N개의 수를 저장할 배열 A와 각..

• format_list_bulleted PS/백준
• · 2023. 7. 9.
• textsms

[백준 / C언어] 15651번: N과 M (3)

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 백트래킹 문제 설명 1부터 N까지의 숫자를 중복 허용하여 M개 골라 나열하는 문제다 이때 나열된 수열은 총 N^M개가 된다 구현 출력할 수열을 배열 arr에 저장한다 1부터 N까지의 숫자를 for 문을 이용해 arr에 넣어주고 함수 NnM을 재귀 호출한다 NnM의 인수로 cnt라는 변수가 사용되는데, 이는 현재 배열에 저장된 수열의 길이를 의미한..

• format_list_bulleted PS/백준
• · 2023. 6. 8.
• textsms

[백준 / C언어] 15650번: N과 M (2)

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 백트래킹 접근 방법 뒤에 나오는 수가 앞에 나온 수보다 커야 한다 따라서 last라는 변수를 두었고, 뒤에 나오는 수는 last보다 더 큰 수가 나오도록 해야 한다 M개의 for문을 사용하는 대신 재귀 함수를 이용해 구현한다 구현 find라는 재귀 함수를 만들었다 변수 num은 현재 수열의 길이를 의미하고 last는 나열된 숫자들 중 가장 마지막..

• format_list_bulleted PS/백준
• · 2023. 6. 7.
• textsms

[백준 / C언어] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 1부터 N까지의 숫자에서 M개를 중복없이 골라 각기 다른 순서로 섞어 나열하는 순열을 만들어내는 문제다 이는 DFS를 활용한 백트래킹으로 해결할 수 있다 우선 출력할 숫자는 배열 arr에 담아두었고 배열 used에는 각 인덱스에 해당하는 숫자가 배열 arr에 저장되었다면 1, 저장되지 않았다면 0을 담았다 그리고 idx가 M이 되면 배열 arr에 저장했던 수를..

• format_list_bulleted PS/백준
• · 2023. 5. 13.
• textsms