본문 바로가기

BOJ39

백준 15651 N과 M (3) 백준 15651 N과 M (3) 1. 문제 링크 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 문제 해결에 대한 아이디어 중복 순열이므로 순열 로직에서 visit을 제외하였다. Input에 따라 Output 양이 많아져서, StringBuilder를 사용하여 시간을 줄일 수 있다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt.. 2021. 12. 31.
백준 15650 N과 M (2) 백준 15650 N과 M (2) 1. 문제 링크 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 문제 해결에 대한 아이디어 조합은 순서와 상관 없이 동일 구성이면 하나로 카운트한다. 따라서 이전 재귀에 접근했던 값을 피하기 위해 다음 재귀로 넘어갈 시, i+1을 한고 visit(중복 방지)을 체크해야한다. Input에 따라 Output 양이 많아져서, StringBuilder를 사용하여 시간을 줄일 수 있다. 3. 코드 import ja.. 2021. 12. 30.
백준 10974 순열 백준 10974 순열 1. 문제 링크 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 해결에 대한 아이디어 문제의 테스트 케이스는 [1, 2, 3]에 대한 순열의 결과이다. visit 을 사용하여, 순열 결과 배열(int[] candidate)에 들어가는 숫자의 순서를 제어한다. 백트래킹으로 모든 순열을 구할 수 있으며, 테스트 케이스 기준으로 아래와 같이 동작한다. (depth를 인데스로 사용하고 있다.) 재귀의 depth별 결과는 아래와 같다. 3. 코드 import java.io.BufferedReader; impor.. 2021. 12. 28.
백준 6603 로또 백준 6603 로또 1. 문제 링크 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 2. 풀이 이 문제는 조합의 대표 유형이다. 조합은 순서를 고려하지 않기 때문에 아래의 경우는 1개로 카운트 한다. - [1, 2, 3] / [1, 3, 2] / [2, 1, 3] [1, 2, 3] 에서 2개를 뽑는 경우를 생각해본다. 가능한 경우는 [1, 2] / [1, 3] / [2, 3] 총 3개이다. 처음 1을 뽑고 나서 1이 포함된 모든 경우.. 2021. 12. 27.
백준 15685 드래곤 커브 - 삼성 SW 역량 테스트 기출 백준 15685 드래곤 커브 - 삼성 SW 역량 테스트 기출 1. 문제 링크 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 2. 문제 해결에 대한 아이디어 1. 이 문제는 드래곤 커브가 어떤 규칙을 갖는지 파악하는게 중요했다. 2. 각 방향은 숫자와 매핑되어 있다 0 : → / 1: ↑ / 2 : ← / 3 : ↓ 3. 드래곤 커브가 세대를 거듭하면서 그려지는 예시를 보면 아래의 규칙을 찾을 수 있다. . 0 세대 .. 2021. 10. 3.
백준 15686 치킨 배달 - 삼성 SW 역량 테스트 기출 백준 15686 치킨 배달 - 삼성 SW 역량 테스트 기출 1. 문제 링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 문제 해결에 대한 아이디어 1. 0개부터 M(최대 남길 수 있는 치킨집)개 까지의 모든 경우를 확인하는 완전 탐색이다. 2. 치킨 집(c)과 집(h)의 거리는 |c.y - h.y| + |c.x - h.x| 2. 어떤 집의 치킨 거리는 가장 가까운 치킨 집과의 거리이다. 3. 각 케이스마다 치킨 거.. 2021. 10. 3.

티스토리툴바