알고리즘 16

[백준/파이썬] 2410번 2의 멱수의 합

http://xn--acmicpc-hu32a.net/problem/2410 이 문제를 해결하기 위해 1부터 8까지 다 적어봤다1 = 12 = 1+1, 23 = 1+1+1, 2+14 = 1+1+1+1, 2+1+1, 2+2, 45 = 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+16 = 1+1+1+1+1+1, 2+1+1+1+1, 2+2+1+1, 4+1+1, 2+2+2, 4+27 = 1+1+1+1+1+1+1, 2+1+1+1+1+1, 2+2+1+1+1, 4+1+1+1, 2+2+2+1, 4+2+18 = 1+1+1+1+1+1+1+1, 2+1+1+1+1+1+1, 2+2+1+1+1+1, 4+1+1+1, 2+2+2+1+1, 4+2+1+1, 2+2+2+2, 4+2+2, 4+4, 8.. 우선모든 수는  이전 더하기 ..

알고리즘 2025.03.26

[백준/파이썬] 3495 아스키 도형

이 문제를 보고 \와 / 문자열인경우 무조건 넓이를 0.5만큼 차지하고, '.'의 경우 \(/)와/(\)안에 있는 경우에만 1로 계산을 해주면 된다. 근데 그 안에 있는지, 밖에 있는지를 구하기가 어려웠다. dfs, bfs..방법을 떠올렸지만 좋지 않아 보였다. 알고보니 '.' 앞에 나온 \또는/의 개수가 홀수개이면 무조건 안에 있는 것이 된다는 사실을 알았다.따라서 해당 열의 \또는/의 개수를 카운팅 해서 홀수개인 경우에만 '.'을 1개 처리 해주면 된다. import sysinput = sys.stdin.readlineh, w = map(int, input().split()) L=[]for i in range(h):    L.append(input().strip())half = 0cnt=0for i ..

알고리즘 2025.03.19

[백준/파이썬] 8394 악수

문제 풀이 방법- n=1, 악수를 하지 않는 경우 1회 있음- n=2, 2번째 사람이 악수를 하는 경우와 하지 않는경우 총 2회- n=3, 3번째 사람이 악수를 하지 않는다면, n=2일때와 같다. 3번째 사람이 악수를 한다면 3번째사람은 무조건 2(n-1)번째 사람과 악수를 하는 것이므로 이때의 횟수는 n=1일때와 같다.따라서 dp[i]=dp[i-1]+dp[i-2]의 점화식이 나온다.  수가 매우 커질 수 있기 때문에, 마지막 자리만 출력하라고 했으므로 (dp[i-1]+dp[i-2])%10한 값으로 넣어줘야한다. 나는 각 횟수마다 숫자가 증가하는 정도를 하나씩 구해보고 있었는데,, 규칙성을 애매하게 찾아서 해결하는데에 어려움이 있었다. import sysinput = sys.stdin.readlinen ..

알고리즘 2025.03.19

[백준/python] 6064번 카잉달력

https://www.acmicpc.net/problem/6064 카잉 달력문제최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 로 표현되고, 11번째 해는 로 표현된다. ..

알고리즘 2025.01.10

[백준/python] 22939번 쿠킹크루

https://www.acmicpc.net/problem/22939 문제밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고민하는 쿠키였다. 그러던 어느날, 고민을 하면서 산책을 하던 킴쿠키는 쿠키나라의 기사단인 쿠키크루를 모집한다는 전단지를 발견하였다. 쿠키크루에 지원하기 위해서는 지원 분야에 맞는 토핑 3개를 몸에 두르고 있어야 한다. 쿠키크루의 지원 분야와 어울리는 토핑은 다음과 같다.침투단(Assassin) - 젤리(J)치유단(Healer) - 초콜릿(C)마법단(Mage) - 베리(B)방어단(Tanker) - 호두(W)킴쿠키는 쿠키크루에 가입하기로 마음을 먹었지만 쿠키..

알고리즘 2024.12.04

[python] 백준 1012번 유기농 배추

https://www.acmicpc.net/problem/1012문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁..

알고리즘 2024.11.27

[python] 백준 12761번 돌다리

문제https://www.acmicpc.net/problem/12761 풀이갈 수 있는 방법을 리스트에 넣어두고, 각 방법을 모두 진행하면서 도착하는 돌의 번호까지의 이동횟수에 ,이전 이전 돌까지의 이동횟수 +1 을 해주면 된다. 우선 갈 수 있는 방법은1, -1, a, -a, b, -b, *a, *b 이다. 해당 방법대로 맨처음 돌번호에 차례대로 진행시켜보자.처음 예제 대로 N, M, A, B가 각각 1, 20, 2, 3이라고 가정하자시작 돌번호(N)이 1이라고 할때, 1 + 1 = 21 - 1 = 01 + 2 = 31 + 3 = 41 - 2 = - 1 (x)1 - 3 = -2 (x)1*2 = 21*3 = 3 갈 수 있는 경우의 수는 이렇게 8가지 이다. 큐에 [2,0,3,4] 순으로 값을 넣어주고, ..

알고리즘 2024.11.24

[python] 백준 30960번 조별과제

조별 과제 https://www.acmicpc.net/problem/30960 [풀이]시도 13명 조의 어색함 값을 다 구하고 2명 조 어색함 값을 모두 구해 적절히(?) 더한다예를 들어 아래와 같은 값이 입력됐다 가정했을때,720 10 9 11 3 18 1 우선 정렬을 해주면139101118201 3 9 10 11 18 20 이 된다. 여기서 세명 조 편성의 경우는A 1 3 9B 9 10 11C 11 18 20이렇게 세가지일 것이다.(다른 경우는 어색함의 값을 최소화하는데에 불리함)A조의 어색함의 값은 9-1 = 8B조는 11-9 = 2C조는 20-11 = 9 가 된다. 각각의 값을 리스트에 넣고 L2 = [8,2,9]for i in range(0,n-2,2): a = L[i+2]-L[i] ..

알고리즘 2024.11.23

[python] 백준 2606번 바이러스

https://www.acmicpc.net/problem/2606문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,..

알고리즘 2024.11.16

[python] 백준 2579번 계단 오르기

계단 오르기https://www.acmicpc.net/problem/2579 문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다..

알고리즘 2024.11.11