목록분류 전체보기 (235)
Machineboy空
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 문제요약 밟지 않은 새로운 알파벳 칸으로만 갈 수 있을 때, 이동할 수 있는 최대 칸 난이도 Gold 4 풀이 포인트 DFS 활용 이전 글자와 중복 체크 REVIEW 아직 문제가 주어졌을 때, bfs와 dfs중 무엇을 선택해야할지 모르겠다. dfs는 감이 오는데 bfs의 경우 아직 낯설다.. 이 문제의 경우 string에 지나온 값들을 누적해주고 그것을 초기화할 시점을 잘못 짚어 모든..
https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 문제요약 한 번의 점프 시, 벽에 닿을 때까지 진동이 상하좌우로 퍼져나간다. 범인을 찾을 때까지 몇 번의 점프를 해야하는가. 난이도 Gold 4 풀이 포인트 bfs 응용 문제 잘읽기 REVIEW 단순한 dfs 문제겠거니 하면서 풀이 시작했는데, 계속 segment fault에 부딪혔다. 정답률이 53%라, 나도 풀 수 있겠거니하고 계속해서 도전하다가 실패했다. 난이도를 확인하니 과연 g..
https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제요약 상하좌우로 피는 꽃 세 송이를 최소 비용으로 심기 난이도 Silver 2 풀이 포인트 백트래킹 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 순열 do while(next permutation) : 순열 돌리며 확인할 수 있는 방법 문자열 대소 비교 '23'과 '123'의 경우 : 앞쪽 한 자리수부터 대소비교를 시작하기 때문에 23이 더 큰 숫자로 판정됨 주의 REVIEW..
https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 문제요약 상하좌우로 피는 꽃 세 송이를 최소 비용으로 심기 난이도 Silver 2 풀이 포인트 dfs 응용 REVIEW 무조건 풀 수 있을 것 같은데 안 풀려서 너무 답답했는데 어찌저찌 하드 코딩으로 해냈다. CODE #include using namespace std; int n, a[11][11], visited[11][11]; vector co; int dx[] = {-1,1,0,0}; i..
https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 문제요약 왼쪽 아래에서 오른쪽 위 꼭짓점으로 이동할 때, 이동 거리가 k인 경우의 수 구하기 난이도 Silver 1 풀이 포인트 경로의 수 누적하기 방문배열 초기화 위치 REVIEW 방문배열에 이동 거리를 누적해 가는 방법에 익숙해 져야 하고, 재귀가 끝나는 시점에 방문배열을 초기화해줘야 하는데, 이 코드의 위치를 찾기가 힘들었다. 한 경로가 끝이나면 방문 ..
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제요약 1칸 좌우 이동, 2배 이동이 가능하고, 도착점도 가속 이동을 할 때, 둘이 만나는 최소 시간 난이도 Platinum 5 풀이 포인트 방문배열, 짝홀을 나눠 생각하는 것 수빈이가 동생보다 먼저 갔던 위치고, 두 번만에 이동이 가능하다면 아니면 한번에 만나거나! REVIEW 어렵다 했더니 과연 플래티넘. 동생위치를 추적하고, bfs를 돌려가며 같은 경우..
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제요약 1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 궤적 나타내기 난이도 Gold 4 풀이 포인트 prev에 계속 쌓아두며 역추적해가는 방법 for문 사용법 for (int next : {now - 1, now + 1, now * 2}) REVIEW 우선 너무 오랜만에 풀어서 using namespace std 구문도 낯설어질 뻔..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제요약 1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 경우의 수 구하기. 난이도 Gold 4 풀이 포인트 bfs 응용 방문한 적 없다면 이동 시간 누적 cnt 배열 경로의 수는 지금까지의 경로의 수에 누적해주는 방식 방문한 적 없다면 현재 위치까지의 경우의 수 + 다음 정점의 경우의 수 방문한 적 있고, 현재 노드에서 간 적 있는 ..