[Java] 백준 1285 (동전 뒤집기) Gold 1

Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Approach Greedy + Bitmask 문제이다. 주요 로직은 다음과 같다. N x N 행렬이고, sum은 뒷면 동전의 총 개수이다. 행을 기준으로 뒤집을 행을 선택한다. (이 부분은 2^n 개수 만큼 존재한다.) 101 이라면 0, 2번째 행을 뒤집는다. 이제 선택한 행들을 뒤집을 건데, 열을 기준으로 먼저 뒤집는다. 101 이라면, 0,1,2 열 순서대로 0번째 행..

→2021.05.21

Algorithm/Baekjoon Online Judge

[Java] 백준 1062 (가르침) Gold 4

Problem : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net Approach 조합(Combination)을 이용한 완전탐색(BruteForce)문제이다. 처음에는 조합을 list로 구현하였으나, 시간초과를 받았다. 그래서 총 알파벳의 개수인 26 크기의 배열을 가지고 사용 여부를 체크하며 조합을 구성하였다. 조합을 구현하기 전에 입력에 따라 간단히 처리할 수 있는 부분들을 짚어보자. N은 주어진 단어의 개수, K개 만큼 문자를 배울..

→2021.05.11

Algorithm/Baekjoon Online Judge

[Java] 백준 2098 (외판원 순회) Gold 1

Problem : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Approach 대표적인 외판원 문제 (TSP: Traveling Salesman Problem) 이다. 어떤 지점 A에서 모든 지점을 돌아 다시 A로 오는 최소 비용 경로를 찾으면 된다. (완전탐색) 시작 지점은 아무 곳에서 시작해도 된다. 어디서 시작하든 최소 비용 사이클은 동일하기 때문이다. 코드의 주석처럼 도시가 4개일 때, 1001이..

→2021.04.16

Algorithm/Baekjoon Online Judge

[Java] 백준 1562 (계단 수) Gold 1

Problem : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach Bitmasking을 이용한 DP문제였다. 그냥 계단수를 구하는 문제를 풀어본 기억이 있어 일단 DP를 떠올렸다. 그리고 보통 사용한 숫자를 체크할 때에는 Bitmasking을 사용했기에 이 문제도 그렇게 접근해 보았다. i자리 계단수를 구하는 방법은 i-1자리 계단수의 끝자리에 +1 한 숫자와 -1 한 숫자를 붙인 계단수의 합이다. 하지만 끝자리가 0과 9인 경우에는 각각 +1한 숫자, -1한 숫자만 고려해야한다. 34가 계단수임을 알고 있으면 343도(-1한 숫자를 붙인 것) 계단수..

→2021.04.13

비트마스크

[Java] 백준 1285 (동전 뒤집기) Gold 1

[Java] 백준 1062 (가르침) Gold 4

[Java] 백준 2098 (외판원 순회) Gold 1

[Java] 백준 1562 (계단 수) Gold 1

티스토리툴바