connecting the dots

문제 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 어렵게 생각하면 한없이 어렵게 느껴지는 문제였다. 주의해야 할 점은 Core에 전원이 연결되지 않는 경우가 있다는 점이다. 처음에는 Core가 모두 선택됐을 때를 재귀함수의 기저조건으로 설정했는데, 알고보니 Core가 아예 선택되지 않을 수도 있었다. 따라서 부분집합을 사용해서 풀어야 한다. 풀이는 다음과 같다. map[][]에 input 값을 받을 때, 가장 바깥쪽 core(이미 연결되어있는 core..

문제 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 입력 가능한 문자들 중 L개를 고른다(조합) 조합 중 모음이 한 개 이상 && 자음이 두 개 이상인 것만 자료구조에 넣는다 해당 자료구조를 sort(알파벳 순으로 정렬) 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java...

문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 여러가지 풀이가 있지만 난 DP로 풀었다 / map[i][j]를 기준으로 해당 위치에 파이프가 가로/세로/대각선으로 위치할 수 있는 경우의 수를 DP로 더해나간다 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main ..

문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 풀이 부모/자식간의 관계를 나타내는 relation이라는 이차원배열을 만들어 부모/자식간이면 1을, 아니라면 0이 들어있도록 한다 visit 체크도 필수 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.u..