Social Developer

어제보다 한 걸음 더

Algorithms

문제를 잘 이해해야겠다. 지문에서 크기가 양수인 부분수열 중에서~ 부분이 있는데 크기가 양수라는 말 그대로 이해하지 못하고, 값을 양수라고 생각했다. 지금 보면 헷갈릴 이유가 없는데, 처음 접했을 때는 이상하게 헷갈렸다. 크기가 양수인 부분수열이라 하면 아무 것도 선택하지 않는 상황만을 제외하면 되겠다. 그런 경우도 부분수열이라고 할 수 있는지는 몰랐지만 아마 집합에서의 부분집합에서 공집합 개념과 유사하지 않은가 싶다. 풀이는 먼저 DFS, 백트래킹 개념을 이용하면 된다. 수열의 각 원소로 구할 수 있는 값을 모두 구하면서, 값이 S와 동일한지 아닌지를 체크하면 되겠다. 시간 제한이 2초로 주어졌는데, 수열의 길이인 N의 최댓값이 20이다. 각 원소를 합에 포함할 지, 하지 않을지 두 가지 선택지를 모든..

2021. 2. 5.

Algorithms

지문은 간단하다. 입력으로 k개의 수를 주기 때문에, 그 k개의 수에서 6개를 골라 사전 순으로 출력하면 된다. 진짜 문제는 k개의 수에서 6개를 고르는 과정과 이를 사전 순으로 출력하는 과정이다. 간단한 것 같은데 은근히 머리가 아프다. 알고리즘 분류에 백트래킹이 있기 때문에 풀이 방법을 떠올리면 다행인데, 이를 모르고 풀이를 떠올리기는 쉽지 않을 것 같다. 어쨌거나 백트래킹을 활용한 DFS라는 것을 떠올릴 수 있다면 구현은 복잡하지 않게 할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P6603 { static int[] S; stati..

2021. 2. 2.

Algorithms

문제를 보고 처음 한 것은 예제 입력을 직접 그려보는 것이었다. 직사각형이 여러개 그려지는 모습이 머릿속에서 잘 안그려졌기 때문.. 그리다가 x, y를 바꿔 그려 다시 그리면서 너무 더러워졌다.... 붉은색으로 입력받은 직사각형을 하나하나 그려주고 번호를 매겨줬다. ???... 겹쳐서 그려지는 직사각형이 있다. 문제에서 펜을 떼는 PU 명령의 최솟값을 구하라고 했고, 거북이가 같은 선을 여러번 그릴 수 있다고 했다. 펜을 떼지 않고 그릴 수 있는 직사각형들은 떼지 않고 그리고, 떼는 횟수를 구하면 될 것 같다. 근데 떼지 않고 그릴 수 있는 직사각형의 정보를 어떻게 담지.. 고민하다 먼저 생각이 든 것은 그려야 하는 좌표들을 Set에 모두 담아두는 것이었다. Set을 생각한 이유는 겹치는 부분들은 중복해..

2021. 1. 29.