본문 바로가기

BOJ

백준 14890 / 경사로 문제 설명에 보강이 필요할 것 같다. 처음엔 가로를 체크하고 세로를 체크한다고 할 때, 가로의 경우에서 경사로를 설치한 곳에 세로의 경우 때 경사로를 설치하지 못하는 건 줄 알았다. 즉, 가로의 경우에서 경사로를 설치한 곳은 세로의 경우에서도 경사로를 설치할 수 있다! (내가 괜히 어렵게 생각한 것일수도...) 문제를 지나갈 수 있는 길의 개수가 아니라, 길이 될 수 있는 모든 경우의 수를 구하는 것이라 해야할 것 같다. 맵을 100,100 크기로 선언해 놓고 문제에서 주어진 n x n을 넘어가는 곳은 전부 200으로 해놓았다. (포문돌때 넘어가는 경우까지 체크하기 귀찮아서..) 차이가 1일때, 경사로가 지어질 곳의 상태를 미리 파악하고, 설치가 가능하면 설치. 설치는 bool 배열을 사용했다. 가로 세..
백준 14503 / 로봇 청소기 시뮬레이션 문제 문제에 나온 그대로 알고리즘을 구성하면 된다. 큐를 사용하되, 1번에서 2번작업으로 넘어가기전 4방향 탐색을 수행해 청소할 공간이 있는지 찾는다. 청소할 공간이 있다면 2-1로, 청소할 공간이 없다면 2-3으로 가되 2-3에서 청소기가 향하고 있는 방향 뒤쪽에 벽이 있다면 break; 없다면 후진을 한다. 부울 배열을 사용하여, 청소를 했으면 true 안되어있다면 false. queue의 while문이 break 됬다면 맵에서 true가 몇개 있는지 찾으면 그거시 정답. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646..
백준 3190 / 뱀 뱀 게임. 예전에 전자사전으로 많이 했던 게임인데, 그 때 그 게임과는 조금 다르다. 이 게임은 대가리가 먼저나가고 꼬리가 그 다음으로 잘리는 방식이다. 즉, ㄷ자로 모양으로 있는 4칸짜리 뱀이 있다고 가정할때, 밑으로 이동하면 전자사전의 게임 경우 죽지 않는데, 이 게임은 대가리가 먼저 나가 꼬리에 부딪혀 죽는다. 그리고.... 문제를 똑바로 읽어야한다. 나 같은 경우는 맨위 왼쪽이 (1,1)이라고 문제에 떡하니 적혀있는데, (0,0)인줄알고 사과의 값을 그대로 받았더니 원래 있어야 할 사과의 위치보다 행+1, 열+1에 위치시켜 헤멨었다. 제발 문제 좀 제대로 읽자! 뱀의 대가리를 중심으로 큐를 사용했고 뱀은 deque를 사용했다. (사과를 먹는 경우 대가리만 늘고 꼬리가 줄지 않아, push_fron..
백준 14499 / 주사위 굴리기 뚝배기 굴리기 일단 문제에 낚시가 있다. 통상적으로 '동서남북'이라 말하지만 이 문제에서는 순서가 '동서북남'이다. ㅈ.. 주사위를 굴리는 알고리즘을 짜야하는데, 시뮬레이션 문제는 항상 시간싸움이기 떄문에, 알고리즘이 생각나지 않는다면 노가다로 때려박는 것이 방법이다. 주사위의 상태를 dice[4][3]의 배열에 담는다 그리고 항상 dice[1][1]을 바닥 쪽, dice[3][1]를 윗 쪽이라 설정한다. 주사위를 남,북 쪽으로 굴리면 +처럼 생긴 주사위에서 l 에 적힌 숫자만 한칸 씩 바뀐다. 예를 들어 문제에 제시된 주사위 상태에서 남쪽으로 이동한다면 숫자가 밑으로 한칸씩 이동한다 2 61 에서 25 16 5 이런 식으로 4방향 모두 선언해주고 문제에 주어진대로 맵과 주사위의 상태를 바꾸어준다. 항상..
백준 10422 / 괄호 다이나믹 프로그래밍 점화식을 생각해내는 것이 굉장히 어렵다. 길이는 L d[n]가 길이 n에서 만들 수 있는 괄호 문자열의 개수라고 가정하자.첫번째 (과 대응되는 )가 i번쨰 위치에 있다고 가정하자. 그렇다면 첫번째 (와 i번째 위치의 ) 사이엔 총 몇개의 경우의수가 있을까. d[i-2] 그리고 i 이후의 문자열엔 몇개의 경우의 수가 있을까. d[L-i] 그렇다면 L을 1부터 5000까지, i를 2부터 L까지 모든 경우에 대해 d[L]에 d[i-2] * d[L-i]를 더해줘야 한다. 내가 짠 코드엔 하나의 꼼수가 있는데 d[0]을 1로 설정해야 제대로 된 정답이 출력된다는 점이다. 원래 d[0]은 0이어야한다. 코드 1234567891011121314151617181920212223242526272829..
백준 5557 / 1학년 다이나믹 프로그래밍 문제 기타리스트 문제와 해결법은 (https://naivep.tistory.com/73) 동일하다. D[n][i] 배열을 n번째 숫자에 도달했을 때 i(0 n; for (int i = 0; i > num[i]; } d[0][num[0]] = 1; for (int i = 0; i
백준 1495 / 기타리스트 지금 5로 연주하고 있고, 다음 곡의 볼륨이 2라면 다음곡은 3과 7로 연주할 수 있다. D[n][i]가 n번쨰 곡에서 볼륨 i로 연주 할 수 있으면 1, 없으면 0이라고 하자. 처음 볼륨이 s라면 D[0][s]=1이고, 첫번째 곡의 볼륨이 3이라면 D[1][s-3] = 1 , D[1][s+3] =1이 되는 식이다. 여기서 s-3이 0보다 크거나 같아야 되고 s+3이 m보다 작아야한다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#include#include#include#include using namespace std; int d[102][1002];int v[1..
백준 12865 / 평범한 배낭 무게와 가치가 주워지는 n개 중 가장 최적의 무게로 최대의 가치를 뽑아내는 알고리즘은 Knapsack 알고리즘(https://naivep.tistory.com/72)이라고 따로 단어가 있다고 한다. D[i][j]를 첫번째부터 i번째까지 물건을 탐색했고, 탐색해서 담은 물건들의 무게 합을 j라고 할때 가중치의 합이다. 여기서 i번째 물건을 담은 경우와 담지 않은 경우가 있는데 담은 경우는 D[i-1][j-w[i]] + v[i]이다. ( w[i]는 i의 무게, v[i]는 i의 가치) 담지 않은 경우는 D[i-1][j] 여기서 모든 j의 경우에 대해 max값을 찾으면 된다. 코드 123456789101112131415161718192021222324252627282930313233343536#include#i..

티스토리툴바