웹개발 성장기

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 반례가 엄청 많이 존재하니 혹시라도 틀렸다면 질문게시판의 반례모음집 게시글을 참조하며 고쳐나가면 좋다. 어떻게 풀지 생각하다 BFS N부터 시작해서 100까지 가는 방법을 찾았다. 문제 분류는 브루트포스로 되어있는데 말 그대로 브루트포스로 0부터 1000000까지 모든 경우를 계산하는 방법도 있다. N에서 출발하는데 현재 숫자가 누를 수 있는 번호이면 (isPossibleToPress(int n)으로 각 자릿수에 누를 수 없는 수가 있는지 ..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 BFS로 네 가지 경우 (DSLR)를 전부 탐색한다. int, String을 저장하는 custom class DSLR을 구현했다. 큐에는 (현재 숫자, 지금까지 부른 명령어)를 저장한다. 탐색하다가 현재 숫자가 B가 되면 지금까지의 명령어를 출력한다. visited[]로 숫자 중복 여부를 확인한다. D, S, L, R을 method로 만들어서 사용했다. 코드 import java.io.*; import java.util.*; public cla..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 시간초과가 났던 문제. 검색하여 찾아보니 연료를 무한으로 충전할 수 있어서 그렇다고 한다. 문제에는 적혀있지 않은 예외사항이 두 가지 있다. 택시 기사가 승객의 위치까지 도달할 수 없는 경우 (거리 = INF) 승객을 도착지까지 태울 수 없는 경우 (거리 = INF) 되는지 안되는지 판단할 때 단순히 거리와 연료량 여부로 판단하면 안되고 이 부분도 고려해야 문제가 통과한다. 구현문제라 문제에 충실하면 생각보다 어렵지 않..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 다양한 방법이 있는 것 같지만 다익스트라로 풀었다. 우선 여행 계획에 있는 도시들은 중복될 수 있으므로 순서를 배열로 입력받음과 동시에 HashSet으로 받았다. HashSet에 있는 도시들만 다익스트라 알고리즘으로 경로를 갱신했다. 만약 위치가 INF로 남아있으면 그 도시로는 방문이 불가능하다는 의미이다. 마지막으로 여행 계획에 있는 도시들을 for문으로 순회하면서 INF가 나오면 바로 "NO"를, 그렇지 않으면 "YES"를 출력하게 했다. 코드 impo..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 일단 이 문제는 다익스트라가 맞다. 틀려서 결국 구글링을 하긴 했는데 대부분 이분탐색과 BFS를 조합하여 했지만 이분탐색으로 풀면 뭔가 문제의 취지에 안맞는 느낌(?)이 들어서 다익스트라 코드도 찾아봤다. 다익스트라로 풀 경우 우선순위큐를 사용하여 중량 기준 내림차순으로 들어가도록 한다. 일반적인 최단경로 찾기의 경우 시작노드 기준 거리 정보를 업데이트를 하는 dist[]을 두는데, 여기선 해당 위..

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 사다리를 코드로 어떻게 표현해야 할지 고민을 엄청 한 문제!! method를 기능별로 만들어서 풀었더니 군더더기 없이 한번에 통과! 이차원 배열을 만들고 한 column을 한 세로선이라고 두었다. 그리고 가로선은 인덱스 값을 줘서 표시했다. 이렇게 한 이유는 만약 1로만 표시하면 내려갈 때 양 옆에 가로선이 존재하면 이게 옆동네 가로선인지 내 가로선인지 알 길이 없다. 따라서 내 가로선인지 바로 구분하기 위해 인덱스를 두었다. 가로선은 3개가 넘어가면 -1..

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 완전 시뮬레이션 문제 = method를 많이 만들어야 함 처음에 뿌요 위치를 큐에 가져온다. (getPuyo()로 구현) 이제 뿌요 있는곳만 터트릴 수 있는지 확인 터트릴 수 있는 얘들 싹 모아서 비우고 맵 정리 한 연쇄가 끝나면 정답 카운트++ 풀기 전 의문점 위에서부터 터짐? 아래서부터 터짐? 동시에 두 개 이상 터지면 어떻게 됨? 동시에 터져야 한다. 여러번 터져도 연쇄는 한 번만 친다. 터지는 뿌요를 찾았다. 이제 이걸 어떻게..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 우선순위큐를 이용한 다익스트라를 3번 실행한 후 경로가 존재하면 최단경로 출력, 없으면 -1을 출력하면 된다. 출발점, 도착점, 거치는 두 정점을 각각 A, B, X, Y라고 하면 A -> X, Y X -> Y, B Y -> X, B 이렇게 각 정점에서의 최단경로를 구한다. 최단경로는 dist[3][N + 1] 이렇게 이차원 배열을 만들어서 저장했다. A -> X -> Y -> B, A -> Y -> X -> B..