컴공과고씨

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 이 문제는 처음에 감을 잘 못잡았다. 처음에는 최소 시간을 구하려는 방법을 생각하니 당연히 답이 나올 수 없었다. 그래서 고민 좀 많이 하고 생각을 바꿔서 시간을 기준으로 해서 각 시간마다 얼만큼의 사람을 통과시킬 수 있는지로 구현을 하여서 심사할 수 있는 인원의 조건을 만족하는 시간 중에서 최소값을 찾아주는 식으로 구현하였다. 중요한 것은 범위가 엄청 크기때문에 시간초과에 걸릴 수..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제를 정리하면 땅 높이를 맞추어 주는 것인데 이제 땅을 쌓는건 1초, 깎는건 2초 걸리고 쌓을 때는 블록이 있어야 쌓을 수 있다. 최대높이가 256이기 때문에 땅을 0으로 고르는, 1로 고르는 ...... 256으로 고르는 시간을 각각 계산해서 비교해주는 식으로 풀었다. 위 방법을 brute force (브루트포스) 무차별 대입이라고 한다. 먼저 높이의 개수를 저장하는 hight 배열을 만들었..

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 시간초과로 못풀어서 어떤식으로 풀어야하는지 처음으로 답을 참고를 했던 문제이다. 그래서 나중에 한번 더 복습이 필요할 것 같다. 아무튼 어떤식으로 풀었고 시간초과가 났으면 어떤식의 해결방법이 옳았는지 보겠다. 처음 푼 방법은 1, 11, 111, 1111이렇게 직접 n으로 나누어가면서 1의 개수를 늘려주어 나머지가 0인것을 찾으면 될거라고 생각했다. 하지만 이렇게 풀면 시간 초과가 걸리기 때문에 나머지 연산 공식을 써주어야한다. 이 문제는 나머지..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제를 보고 탐색으로 풀어야겠다고 생각했다면 바로 풀 수 있다. 한가지 조금 다른 문제와 다른거는 대각선으로 땅을 밟을 수 있기 때문에 대각선을 고려해야한다는 것만 주의해주면된다. 기존에 상하좌우를 dx[] = {0,0,-1,1} = dy[] = {1,-1,0,0} 이런식으로 4번을 반복해서 움직여주었다면 이번거는 dx[] = {0,0,-1,1, 1,1,-1,-1} = dy[] = {1,-1..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 이 문제는 어떤 식으로 접근했냐면 한 로프를 사용한다고 가정했을 때, 자기보다 많은 무게를 드는 로프는 결국 자신의 로프의 최대 들 수 있는 용량을 모두 들 수 있다는 것을 이용했다. 10 30 50 50 85 90 이라는 무게를 들 수 있는 로프가 있을 때 10로프를 이용해서 들 수 있는 최대 중량은? 10과 10보다 큰 로프의 개수를 10에 곱해주면 총 60을 들 수 있다. 30로프를..

https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 이 문제를 보고 조금 생각을 해본 결과 팁을 많이 주고 싶어하는 사람들을 앞쪽에 세워야지 가장 많은 팁을 얻을 수 있다. 왜냐하면 뒤로 등수가 밀릴수록 그 만큼 빼주어야한다. 그렇다면 팁을 10을 주고 싶은사람이 10등인것과 팁을 1을 주고싶은 사람이 10등이라면 전자는 0원 후자는 음수가 되어진다. 여기서 음수는 0으로 처리가 되어지기 때문에 둘다 똑같이 못받는 꼴이 된다. 그..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수를 구하는 문제. 문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다. 재귀로 구현하면 아마 시간초과가 걸릴것이다. 그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 이 문제는 탐색 문제지만 고려해야할 것이 있다. 첫번째는 무조건 적인 탐색이 아니라 외부쪽에 있는 치즈를 전부다 방문하면 카운트 그 다음 안쪽에 있는 치즈 전부 탐색 후 카운트 이런식으로 순차적으로 가면서 카운팅을 해주어야 된다. 그래서 나는 bfs안에 기본적인 구조가 큐를 한번 쓰는 거라면 큐를 2번을 사용하여 구현을 해주었다. 일단 (0,0)에서 시작을 해서 탐색을 시작하여 1을 만났을 때는 temp큐에 넣어주고..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제 같은 경우 처음에는 계산 형식으로 고민을 하다 bfs를 써야겠다는 생각이 들었다. bfs를 쓰니 간단히 해결이 되었다. bfs 구성은 동생을 찾지 못하면 x+1, x-1, 2x를 visit에 넣어 방문했는지 검사한 후 방문을 하지 않았다면 각각을 q에 넣어주면 간단히 해결된다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이 문제는 일반 탐색문제와 거의 흡사하지만 고려해주어야 할게 하나 더 추가된 형식이다. 바로 층 수가 있다는 것이다. 보통 탐색 문제의 경우 상하좌우만 움직여 좌표를 2개만 설정해주지만 이 문제 같은 경우 층 수도 고려를 해주어야 하기 때문에 층을 고려하는 좌표를 하나 추가해주어 풀어주면 간단히 해결된다. 나는 bfs를 이용하여 큐에 x,y,z,count를 튜플로 만들어 넣어주어 문제를 해결하였다. b..