C++61 백준 1697 숨박꼭질 c++ 이번문제는 최단시간을 찾는것.수빈이가 움직일수있는건 현위치에서 1. 현위치 + 12. 현위치 - 13. 현위치 * 2 이걸 bfs로 풀면 아주 간단해진다. 먼저 위치의 범위를 초기화 해준다. 그 후 수빈이의 초기위치를 0으로 할당한다.(수빈이가 그 지점에 존재한게 0 초일때니까) 큐에 수빈이 초기 위치를 넣고 수빈이가 움직일수 있는 조건1~3 을 반복하면서 문제없으면 죄다 큐에 집어넣는다.수빈이 이덩위치가 동생위치 b이면 그때 그 지점에 할당된 숫자가 걸린 최단시간이다.먼저 수진이 무빙은 temp1~3으로 두고 한번 수진이가 도착한지점에 대해 3번 동작을 한다.for문을 돌며 0~100000 범위를 벗어나면 수빈이가 갈 수 없는곳이니 패스. (갔다는건 새로 큐에 넣겠다는것)그리고 새로 가는곳엔 현위치에서.. 2024. 10. 24. 백준 3015번 오아시스 재결합 c++ 첫 플래티넘 문제이다. 생각보다 간단한데? 하고풀었을때 예외케이스들이 계속 생겼다. 역쉬플래 이 문제는 서로눈을 볼 수 있는가. 즉 둘 사이에 둘보다 큰 사람이 있으면 안된다!이말은 키가 1, 2, 3이면 1 과 3은 서로 못본다. 2는 3보다는 작지만 1보다는 크기 때문!시간제한이 1초이고 n이 최대 500,000 이기에 O(n^2)면 시간초과다. 테스트 케이스를 보면서 이해해보자. 1) 2가 들어오고 4가 들어오면 일단 2-4 쌍이 생긴다. (누적 1쌍) 2 42) 그 뒤에 1이 쌓이면 4-1 쌍이 추가로 생긴다. (누적 2쌍) 2 4 13) 그뒤에 2가 쌓이면 1-2, 4-2 두 쌍이 생긴다 (누적 4쌍) 2 4 1 2여기까지만 봤을때 쌍이 생기는 조건을 보면 새로운 데이터보다 큰 곳 까지.. 2024. 10. 15. 백준 6198 옥상정원꾸미기 c++ ver.2 이것도 전에 풀었으나 다시 새로푼다. 좀더 간결하고 생각 잘해서 지저분하지 않게.. 왼쪽부타 각각의 건물이 존재한다.각각의 건물이 몇개를 볼 수 있는지를 카운팅 하는것도 좋다. 하지만 왼쪽부터 스택에 넣으면서 몇개의 건물이 방금 스택에 넣은 건물을 볼 수 있는지를 보면 간결해진다. 맨 왼쪽에 탑을 일단 스택에 넣는다.두번째 탑을 넣기 전에, 두번째 탑이 첫번째 탑보다 같거나 크면 첫번째 탑을 스택에서 삭제시켜준다.사실 예를들어서 첫번째탑을 삭제하는거지 그냥 자기보다 작은게있으면 싹다 지워준다.그리고 푸시하기 직전 스택에 쌓여있는 개수를 카운트하고 푸시한다. #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0).. 2024. 10. 11. 백준 2493 탑 c++ ver.2 이미 4개월전에 푼 문제인데 뭔가 찝찝해서,, 발상이 좀 정형화(정형화? 간결함?) 될 필요가 있을거같다. 쉽게 생각해서 왼쪽부터 왼쪽에 자기보다 큰 애가 있으면 걔만 신경쓰면 된다. 큰애중 가장 가까운 애만!그리고 출력은 그 가장 가까운 애의 인덱스 번호다! (문제에선 서로다른높이라고 명시했기에 같은높이는 경우가 없다.)일단 왼쪽에 자기보다 큰 애가 있지 않을경우를 대비해서 가상의 엄청 큰 벽을 만들어준다.(인덱스 번호는 0)100000001이 입력값 최대범위보다 1만큼 큰 값이기에 든든한 0번위치의 방벽이다. 자 그다음 모든 기둥은 자기보다 큰 바로직전의 벽 번호만 알면 된다.1번 입력값은 무조건 방벽에 막혀서 0번인덱스를 출력한다.자 2번타자가 들어올때 1번이 자기보다 작으면? 1번 그냥 삭제시켜도.. 2024. 10. 11. 백준 4179 불! c++ 이 문제를 보면 퍼져나가는 불이 있고 동시에 움직이는 J가 있다.J와 불 모두 사방으로 움직일 수 있다. J가 탈출하는 최단거리(탈출못할수도있음)를 구해야한다. 여기서 불도 퍼지고 J도 움직여야 하는데 이전에는 bfs로 풀때 큐를 이용했었다. 여기서도 마찬가지로 큐를 이용해서 한번 퍼질때 차례대로 집어넣고 움직인 요소들을 다시 큐에집어넣음으로써 확장시킨다.그러나, 사람(J)이 움직인건지 불이 퍼진건지 구분이 필요하다.그래서 입력값을 받을 board[][]를 준비하고불의 위치 추적을 위한 fire[][]도 준비하고사람이 방문한 위치 visit[][]도 준비한다. 사방면 이동 좌표변화량인 dx[] dy[]도 준비한다. 먼저 fire은 전부 0으로 초기화 해준다. 불이 퍼진곳은 1을 할당 할 것이다 me.. 2024. 10. 10. 백준 7576 토마토 c++ 이 문제를 읽어보면 마치 좀비바이러스 같다는 느낌을 받는다.어제의 아군이(안익은 친구) 오늘의 좀비가 되..(익어버림) 이번에는 M이 가로이고 N이 세로이다. 즉 m을 열로 제공한것. 헷갈리면 안됨. 그래서 이렇게 했다. 주요 사용 변수는board[][] //처음 인풋으로 초기상황 저장하는 변수visit[][] // 하루가 지날때마다 퍼져가는 상황 추적. 여기서는 방문 뿐만 아니라 며칠지났는지를 저장. date //전부 감염된 최솟값 저장.세가지이다. ps. dx,dy변수로 사방면 접근 https://ilovecomputerscience.tistory.com/entry/%EB%B0%B1%EC%A4%80-2178-%EB%AF%B8%EB%A1%9C-%ED%83%90%EC%83%89-C 백준 2178 미로.. 2024. 10. 8. 이전 1 2 3 4 ··· 11 다음
