순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/2780 2780번: 비밀번호 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라. www.acmicpc.net 문제 : 길이 n 자리의 비밀번호를 만들 수 있습니다. 그러나 항상 인접한 번호만 누를수 있습니다. 이때 n이 주어질때 n자리의 비밀번호를 만들 수 있는 경우의 수를 구하시오 해설 : 다이나믹프로그래밍 문제입니다. 현재 '1'이라는 숫자를 눌렀다면 '2','4' 둘 중 하나를 누를 수 있죠. 이를 뒤집어서 생각해 보면 현재 '2'를 누르기 위해선 반드시 그 전에 '1','5','3' 중 하나를 누른 상태여야 된다는 것 입니다. 그..

www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 문제 : 회전하는 배열을 주어진 범위에 맞게 예쁘게 출력해라 해설 : 다른 분들보면 어떻게 공식을 도출해서 풀었던데 난 모르겠음;;;; 그래서 그냥 노가다로 품. 노가다로 푸는 방법도 효율적이게 문제에 접근해야 된다. 단순히 10000x10000 배열을 잡고 수들을 채우고 범위에 맞는 수들을 출력하게끔 하면 되겠지!!!라고 생각하면 안된다. 이유는 제한 메모리는 128MB 바이트인데 10000x10000 배열을 잡으면 범위를 넘어서기 때문.... 그러면 어떻게 해야되는 건가? 0 c1 >> r2 >> c2; go(r1, c1, r..

www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 문제 : 호석이가 도미노를 무너뜨린다. 이때 길이-1 만큼 넘어지고, 연다라 넘어진다. 넘어뜨린 후에는 한개의 도미노를 원상태로 만든다. 각 라운드마다 점수를 출력하고 보드의 상태를 출력해라 해설 : 뭐 해설이라고 할 것 없이 문제 그대로 구현만 침착하게 잘해주면 됩니다. 입력받은 보드를 직접적으로 사용하시게 되면 일관성이 깨져버리니 복사하여 그 복사한 보드를 가지고 열심히 동작시켜주면 됩니다. ..

www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 문제 : 1번 노드는 모든 노드와 연결이 되어있고, 나머지 노드들간 관계가 주어진다. 이때 어떤 한 노드를 제거하더라도 모든 노드가 연결되어 있는 상태가 되도록 간선을 연결해라 해설 : 어떤 한 노드를 삭제했을때 모든 노드가 연결되게끔 해주면 되니, 한 노드를 하나씩 삭제해보고 mst를 만들면 되겠죠. 처음에 이렇게 풀었습니다. 그러나 시간이 어마어마하게 나오더라구요;;; 아마 삭제..

www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 : 파이어볼이 격자판에 존재하고 상태들을 입력받습니다(좌표,질량,속력,방향) 그리고 파이어볼은 상태의 조건에 맞게 움직입니다. 이때 주어진 단계를 수행합니다(단계는 귀찮아서 안적을게요;;;) 이때 k번의 반복작업을 수행한 후 남아있는 파이어볼의 질량의 합을 구하세요. 해설 : 지난 하반기 삼성문제였더라구요,,,,,(어쩐지 씨xxxxx ,,,,빡쎄더라 ㅠㅠㅠㅠ) 이런 ..

www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문제 : 문자가 적혀있는 판이 주어지고 이동할 수 있는 k 값이 주어집니다. 이때 주어진 문자열을 만들수 있는 경우의 수를 구해라! 해설 : 정말 너무너무 싫고 어려운 다이나믹 프로그래밍 문제입니다. 전 dp 정말 몬해용,,,,ㅠㅠ 일단 정말 간단하게 생각해서 단순히 dfs,bfs 를 사용해서 하나씩 탐색해서 구할 수도 있겠죠. 그러나, 문제는 항상 '중복'입니다. ex) ..

www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 : 팰린드롬 만들기까지 문자열 뒤에 몇개를 붙여 만들 수 있는가? 해설 : 팰린드롬 진짜 너무 싫네요 ㅠㅠㅠ 한번 꼬이면 반례가 안보여.....ㅠㅠ 먼저 필자는 팰린드롬이 무조건 '홀수'여야 된다고 잘못 생각했음.(멍청한 자식) 짝수도 되죠,,,, 맨 마지막 문자를 기준으로 모든 경우의 수를 확인해 보는 방식으로 풀었습니다. 1 - 0(L)번 인덱스와 맨 마지막 문자(R) 2 - 1번 인덱스와 맨 마지막 문자 ..

www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 문제 : 두 로봇이 있고 같은 통로에 존재하도록 할때 소요되는 거리의 최소값을 구해라 해설 : n개의 정점이 주어지고 n-1개의 간선이 주어질때 무조건 '트리'라는 것을 파악할 수 있어야 된다. 어쨌건 두 로봇은 무조건 같은 통로에 있어야 하니 둘 사이에는 간선이 1개만 존재해야한다. 이는 x->y까지 가는 경로중에 가장 가중치가 높은 간선 1개만 빼주면 된다는 뜻. 정점을 하나씩 탐색해주고 목표(y)..

www.acmicpc.net/problem/16569 16569번: 화산쇄설류 첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N)) 그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N) 그 다음 줄부터 M개의 www.acmicpc.net 문제 : 지정된 시간에 화산이 터지고 이 화산은 인접한 칸에 점점 퍼진다. 이때 윤재상이 갈 수 있는 곳 중 가장 높은 고지대의 높이와 도달하기까지 시간을 구해라 해설 : "t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다." 이 말은 화산쇄설류가 인접한 칸으로 1초마다 점점..

www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 문제 : 수직선이 주어지고 [시작점,끝점] 이 주어진다. 선분은 겹칠 수 있고, 이때 그려지는 선분의 총 길이를 구해라 해설 : 간단히 생각해서 선분이 겹칠 경우만 잘 걸러주면 된다. 문제에서 x 값이 증가되는 순서대로 주어진다고 했으니 선분이 서로 겹치는 경우는 단 하나 밖에 없다. 후에 들어오는 x 좌표가 기존에 존재하는 좌표의 y 값보다 작거나 같을때 [x1] ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ [y1] [x2] ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ[..

www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 문제 : 'E' 와 'W'가 주어지고 선물을 구사과님이 어느 칸에서부터 시작하더라도 먹을 수 있도록 배치해야된다. 이때 최소의 선물만 배치해야된다. 해설 : 'E'로 시작하면 'W'를 만나지 않을때까지 전진한다. 그리고 'W'를 만나면 다시 돌아간다. 이는 'E'의 끝에 선물을 하나 놓으면 이 위치를 기준으로 왼쪽으로는 'E' 오른쪽으로는 'W'는 무조건 선물을 먹게 된다는 뜻. ex) EEEEEE..

www.acmicpc.net/problem/11565 11565번: 바이너리 게임 첫 번째 줄에는 문자열 a, 두 번째 줄에는 문자열 b가 주어진다. 두 문자열은 0과 1로만 이루어져 있으며, 문자열 a와 문자열 b의 길이는 1 이상 1,000 이하이다. www.acmicpc.net 문제 : 문자열 a,b가 주어지고 a를 b로 만들 수 있는가?를 묻고 있음. 규칙 1 : 맨 앞문자를 지울 수 있음 규칙 2 : 맨 뒤에 문자를 추가할 수 있음. 이때 1이 홀수개이면 1을 나머지는 0을 추가 해설 : 와,,,이런문제 너무 싫어요....근데 또 재밌어 ㅋㅋㅋ(전형적으로 codeforces 에서 나올 법한 문제) 문제에 말리면 절대 풀 수 없는 문제. 결론부터 말하면 a와 b가 어떻게 생겨먹었든 전혀 상관 없다..