본문 바로가기
728x90
반응형

분류 전체보기140

[백준] 6359번: 만취한 성범 - python https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다. www.acmicpc.net 작년 아는 친구 형이 삼성SDS 최종 면접에서 물어봤다고 한 알고리즘 그래서 열심히 풀었다. 해보니 나눠지는 약수의 개수가 홀수 개이면 열려있는 걸로 판단하여 아리스토테네스 체를 활용하여 계산한 다음 마지막에 홀수인 것만 카운트 하여 출력하는 로직으로 설계하였다. T = int(input()) for _ in range(T): cnt = 0 n = int(input()) #n개의 방 0은 닫 1은 열림 arr = [0] * (n+1) #1라운드 1 1 1 1 1 #2라운드 1 0 1 0 1 #3라운드 .. 2024. 4. 3.
[백준] 10844번: 쉬운 계단 수 - python https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음 생각한 아이디어 처음에 무지성으로 고딩때 풀던 점화식마냥 찍어서 작성한 코드. 무지성 찍기가 난이도가 높아질 수록 통하지 않는 듯 하다. n = int(input()) dp = [0] * (n+1) dp[1] = 9 dp[2] = 17 #12 23 34 45 56 67 78 89 * 2 + 10 for i in range(2, n+1): dp[i] = (dp[i-1]-1) * 2 +1 print(dp[n]) 그다음 생각한 아이디어 전에 푼 정수 삼각형처럼 값을 계속해서 증가 시켜가면서 작성하면 어떨까 라는.. 2024. 4. 3.
[백준] 1932번: 정수 삼각형 - python https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 처음 아이디어 왼쪽과 오른쪽 인자를 비교하여 큰 것을 저장하며 값을 저장한다. 틀린이유 작은 것을 선택했을때 마지막에 값이 더 큰 경우의 수가 존재한다. n = int(input()) arr = [] dp = [0] * (n+1) for i in range(n): arr.append(list(map(int, input().split()))) dp[0] = arr[0][0] high = 0 for i in range(1,n): if arr[i][high+1] > arr[.. 2024. 4. 2.
[백준] 7576번: 토마토 - python https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 토마토가 있는 곳을 찾아서 그 부분부터 BFS를 진행하여 나머지 토마토를 찾아 여행을 떠난다. 그 과정에서 토마토의 자리에 전에 있었던 값을 계속해서 더해 나가면서 상자 전체를 탐험한다. 그 후에 만약 토마토가 안익은 자리가 있으면 -1을 하면서 break를 걸어주고 아니라면 최대값을 찾아 출력해준다. 약간 응용 BFS이긴 했지만 아래 부분을 사용하여 경로 길이를 계산하는.. 2024. 4. 2.
728x90
반응형

티스토리툴바