본문 바로가기

백준

 (221)
C++[백준]22342번 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 솔루션 맞왜틀로 골머리를 앓았다. DP 문제인 건 알겠으나, r-1, c-1 r , c-1 r+1, c-1 중에서 최대 값을 저장 값으로 해 주었으나 어딜 틀렸는지 모르겠어 머리를 쥐어짜다 이리저리 수정하다 보니 성공했다. 일단 점화식이 다음과 같은 3가지 경우만 나눠지는 이유는 저장 값은 -1보다 더 이전 열에서 갖고 올 수 있지만 -1에서 더 이전의 열에서 가장 높은 저장 값을 가져와 저..
C++[백준]14846번 직사각형과 쿼리 https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 솔루션 특정 인덱스(x,y)에서 1~10의 수를 몇개씩 갖고있는지 저장해둔다. 나는 구조체 내부에 배열을 선언하여, 1~10까지 몇 번 등장했는지, 저장해둔다. 특정 인덱스에서의 등장횟수를 찾는 법은 1. 현재 인덱스에 배열의 값을 ++ 2. [x-1][y]에서의 등장 횟수 + [x][y-1]에서의 등장 횟수 - [x-1][y-1]에서의 등장횟수를 해 주면 특정 인덱스에서의 총..
C++[백준]1658번 돼지 잡기 https://www.acmicpc.net/problem/1658 1658번: 돼지 잡기 첫째 줄에 돼지 우리 숫자를 나타내는 M(1≤M≤1,000)과 손님들의 숫자를 나타내는 N(1≤N≤100)이 공백으로 구분되어 주어진다. 돼지우리는 1번부터 M번까지의 숫자로 매겨져 있고 손님 역시 1번부 www.acmicpc.net 문제가 좀 조건대로 하면... 안풀리는 것인데 풀리니 이상하다 생각을 하고 푼 문제. (솔루션을 봤음..) 처음에 조건 3.을 제대로 보지 않아서 소스 - 돼지우리 - 사람 - 싱크 이렇게 노드를 연결하여 풀 수 있을 것이라 생각했다. 그런데 문을 열었을 때, 남은 돼지를 적절히 재분배 할 수 있다는 조건이 상당히 까다로워졌다. 도저히 문제를 해결못해서 솔루션을 봤다. 원래라면 디닉으로..
C++[백준]1996번 지뢰 찾기 https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 솔루션 입력으로 들어오는 문자열을 따로 저장해 두고, 2중 for문을 돌면서 8방위에 '.'이 아닌 것이 있다면 무조건 숫자이기 때문에, 숫자로 변환해주어 더해준다. 8방위로 탐색을 할 때는 int dx[8] = { 1,0,-1,0,1,-1,1,-1 }; int dy[8] = { 0,1,0,-1,1,-1,-1,1 }; 각각의 방향을 배열에 저장해 두고 for문을 돌면 더욱 간..
C++[백준] 1761번 정점들의 거리 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 솔루션 트리의 최소 공통 조상을 이용해서 풀었다. 노드를 NlogN 시간에 찾아야 할 것 같아서 희소 배열을 이용했는데, 각 간선을 모두 입력을 받고 난뒤, 거리와, 해당 부모노드를 저장 해 놓고, 희소배열을 채워 넣는다. 1> w; edge[str].push_back({ end,w }); edge[end].push_back({ str,w }); } makeParent(1, 1); mak..
C++[백준] 25402번 트리와 쿼리 https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 알고리즘 스터디..에서 진행한 문제이다. 처음에 문제 제목이 트리와 쿼리가 되어 있어서 세그먼트 트리인줄 알았으나, 그게 아니었다. 솔루션 N이 250,000이고, Q가 100,000이다.. 엥간하게 돌려서는 맞출 수 없겠다고 생각했는데, K의 총 합이 1,000,000인 것을 보았다. 이건 분명 큰 힌트라고 생각하고, 그러니, 쿼리마다 뭔가를 수행하는 것 보다, N이 들어왔을 때 무언가..
C++[백준]16435번 스네이크버드 https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 솔루션 어떤 높이에서 시작해서 자신보다 높이가 낮거나, 같은 과일을 먹을 수 있다고 한다. 나는 이를 정렬을 통해서 풀었다. 정렬을 해서, 가장 높이가 낮은 나무부터 먹으면서 높이를 1씩 증가 시킨다. 만약 먹지 못한다면 그 다음 과일은 못 먹는다. 코드 #include #include using namespace std; int N,M; int..
C++[백준]26004번 HI-ARC https://www.acmicpc.net/problem/26004 26004번: HI-ARC 첫째 줄에 문자열 $S$의 길이 정수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 문자열 $S$가 주어진다. 문자열 $S$의 모든 문자는 영어 대문자이다. www.acmicpc.net 솔루션 각 알파벳을 세어주고, H,I,A,R,C중에서 가장 작게 나온 값을 출력하면 된다. 알파벳을 세어주는 것은 입력으로 들어온 알파벳에 -'A'를 해 주면, 배열을 26칸으로 모든 알파벳의 등장횟수를 알수있다. 코드 #include using namespace std; int N; string str; int alpha[28]; int main(){ cin>>N; cin>>str; for(in..

티스토리툴바